剑指offer-和为S的两个数字

题目描述

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

输出描述:

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

思路

这一题刚开始看到了递增、排序等字眼就瞬间想到了用左右窗口来解决，但是题目要求多对数字和为S时，找到两个数乘积最小的，这个地方困扰我了好久，后来看到了用数学公式推的方法（自己写算法很少会想到用数学推理，都是上来用工程或者语言的特色思维去想。。。）a+b=sum,a和b越远乘积越小，而一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。如果是乘积最大的情况就是一直找到两个指针重合，每次找到一个就将之前返回的结果向量清空然后更新为新找到的。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (array == null || array.length < 2) {
            return list;
        }
        int i=0,j=array.length-1;
        while(i<j){
            if(array[i]+array[j]==sum){
            list.add(array[i]);
            list.add(array[j]);
                return list; // 这种乘法，乘积最小的肯定是第一组（假设a<b a*b<(a+1)*(b-1) 所以第一次找见的序列就是要找的序列）
           }else if(array[i]+array[j]>sum){
                j--;
            }else{
                i++;
            }
             
        }
        return list;
    }
}