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

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

 

 

 

数列满足递增，设两个头尾两个指针i和j，

 1、若ai + aj == sum，就是答案（相差越远乘积越小）

 2、若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1

 3、若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1

      时间复杂度  O(n)

其实主要思想是两个数的乘积要最小，那么这个时候我们就需要知道，当一个有序的序列，两个数相隔越远，最后得到的数最小。所以我们设定两个指针，分别从序列的两头出发。

所以这种思路,第一次找到的答案,就是最小,不同额外考虑其他满足的两个数

有负数也是第一组乘积最小。和一定两个数，其乘积是倒抛物线，越远离对称轴越小，与正负无关

 

找到的第一组（相差最大的）就是乘积最小的。可以这样证明：考虑x+y=C（C是常数），x*y的大小。不妨设y>=x，y-x=d>=0，即y=x+d, 2x+d=C, x=(C-d)/2, x*y=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4，也就是x*y是一个关于变量d的二次函数，对称轴是y轴，开口向下。d是>=0的，d越大, x*y也就越小。()

1 import java.util.ArrayList; 2 public class Solution { 3     public ArrayList
      
        FindNumbersWithSum(int [] array,int sum) { 4         ArrayList
       
         list = new ArrayList
        
         (); 5         //考虑特殊情况,这里array.length要考虑是否小于2了,而不是平常的1 6         if (array == null || array.length < 2) { 7             return list; 8         } 9         //定义最左指针i和最右指针j10         int i=0,j=array.length-1;11         while(i
         
          sum){17                 j--;18             }else{19                 i++;20             }21         }22         return list;23     }24 }