[42] 和为 S 的两个数字(中等)
[42] 和为 S 的两个数字(中等)

题目描述

输入一个递增排序的数组和一个数字 S,在数组中查找两个数,使得他们的和正好是 S,如果有多对数字的和等于 S,输出两个数的乘积最小的。
对应每个测试案例,输出两个数,小的先输出。
输入:[1,2,4,7,11,15],15
返回值:[4,11]

解题思路

双指针

用两个指针指向头尾下标,每次拿两个指针下标所在的数相加,如果大于目标数,则说明尾指针太大,向前走一步,反之亦然。如此一来,和等于目标数的两个数一定是最小的。
/**
 * 双指针
 * T(n) S(1)
 */
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> result = new ArrayList<>();
    if (array.length == 0) {
        return result;
    }
    int a = 0;
    int b = array.length - 1;
    while (a < b) {
        int s = array[a] + array[b];
        if (s == sum) {
            result.add(array[a]);
            result.add(array[b]);
            return result;
        } else if (s > sum) {
            b--;
        } else {
            a++;
        }
    }
    return result;
}