题目描述

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

输出描述

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

求解过程

• 首先注意题目要求，数组是有序，其次要求和相同的要乘积最小那么根据这两个信息可以得到一些东西。
• 数组有序可以考虑二分（减少时间复杂度），和相同要乘积最小那么可以举个例子来考虑，加如我们需要的和为10，那么可以组成10的数字分别是1/9,2/8,3/7等等，从这些数据中可以看出1/9乘积最小满足题目中所述，那么可以推导出两个数的和相同，乘积最小的两个数字是相隔最远的两个数
• 根据上面得出的结论可以考虑从有序数组第一个元素开始对数组遍历，只要找到第一对数那必然是最后的结果。从下标0开始，此时我们假设当前array[i]就是我们要求的结果中的一个数，那么另一个数就应该是target=sum-array[i]，现在要做的事就是从下标low+1到数组最后找到是否存在这样一个数，存在那么就解决了，不存在那就要继续遍历，是不是经典的二分查找了(有序数组，下标，target)
• 此时还需要考虑当我们从左往右遍历的时候那么右边的数字会随着low下标增大，high下标的范围会缩小（因为和是固定的），那么我们二分查找的范围就可以固定到low+1-high之间查找target并返回对应下标如果查找不成功就返回二分查找中最后的高位下标作为下一次循环的high（下面解释为什么这么做）
• 如果查找成功那么返回了命中下标直接存储结果就可以跳出循环了，但是如果查找失败我们就会进入下一次小的数固定查找，根据二分查找失败的条件是低位索引高于了高位索引都没有命中，那也就是说当前查找失败的高位索引一定是最靠近target的值，此时我们将高位索引返回虽然会比target小一些，但是因为下一次循环会增大较小的值，较大的值根据和不变也会减小，所以刚好符合要求，将此时二分查找的高位索引作为下一次的high可以加快搜索减少时间复杂度

解题源代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        if (array==null || array.length==0) return result;
        int low = 0;
        int high = array.length-1;
        while (low<high) {
            int rest = sum - array[low];
            high = getTarget(array, low+1, high, rest);
            if (array[high]!=rest) low++;
            else {
                result.add(array[low]);
                result.add(array[high]);
                break;
            }
        }
        return result;
    }
    
    private static int getTarget(int[] array, int start, int end, int target) {
        int low = start;
        int high = end;
        while (low<=high) {
            int mid = low + (high-low)/2;
            if (array[mid]==target) return mid;
            else if (array[mid] > target) high = mid-1;
            else low = mid+1;
        }
        //未找到，将较小的下标值返回
        return high;
    }
}