剑指Offer_42_和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

解题思路

利用两个指针分别指数组开始和结尾，然后将两指针的值相加，大于给定值，那么尾指针向前移动，因为此时，如果移动开始指针，那么所有的值和结尾指针相加都大于给定值。同理，比给定值小，那么向后移动开始指针。与给定值相同的就是要找的值。

实现

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int f = 0, l = array.length - 1;
        int mlt = Integer.MAX_VALUE;
        while (f < l){
            int fn = array[f];
            int ln = array[l];
            if (fn + ln > sum){
                l --;
            }else if (fn + ln < sum){
                f ++;
            }else {
                if (fn * ln < mlt){
                    mlt = fn * ln;
                    list.clear();
                    list.add(fn);
                    list.add(ln);
                }
                f ++;
            }
        }
        return list;
    }
}