剑指 Offer - 42 - 和为 S 的两个数字（排序数组）

Question

题目

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

解析

比较简单的双指针题目。肯定不是两重循环找。

思路

• 设两个指针 L、R ，分别是排序数组的开头和结尾；
• 然后下面就是两个指针 L、R 向中间靠拢的过程。① 如果 arr[L] + arr[R] > sum ，说明右边那个 arr[R] 大了，需要向左移动，看能不能找到更小的 arr[R] 来和 arr[L] 一起组成 sum 。② 同理，如果 arr[L] + arr[R] < sum ，说明左边那个 arr[L] 小了，需要向右移动，看能不能找到更大的 arr[L] 来和 arr[R] 一起组成 sum 。③ 否则等于就返回即可；
• 题目说要找到乘积最小的，可以发现， L、R 隔的越远， arr[L] * arr[R] 乘积越小，所以我们的做法没问题。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        int L = 0, R = array.length - 1;
        while(L < R){
            if(array[L] + array[R] == sum){
                res.add(array[L]);
                res.add(array[R]);
                return res;
            }
            if(array[L] + array[R] < sum) L++;
            else R--;
        }
        return res;
    }
}