剑指offer-42

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

普通解法：选一个数，然后从它开始往后移动，看看哪个数和他相加等于sum，时间复杂度高。

标准解法：类似上一题的滑动窗口，因为都是有序，所以且窗口变化对应结果大小的变化规则也是一样的（范围变大和变大，总体右移和变大）所以这一题里面也是类似的：窗口两端和大于sum，则右边指针后移，窗口两端和小于sum，则左指针前移。

注：输出乘积最小的两个，其实就是输出最外层的两个，按照上面两种方法，找到第一对就ok了

普通方法

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> ans = new ArrayList<>();
        int l = array.length;
        for(int i=0;i<l;i++){
            int a = array[i];
            int b = sum - a;
            for(int j=i;j<l;j++){
                if(array[j]==b){
                    ans.add(a);
                    ans.add(b);
                    return ans;
                }
            }
        }
        return ans;
    }
}

标准方法

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

        return ans;
    }
}