题目描述

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

解题思路：

        首先定义两个变量min和max，分别指向数组array中的第一个元素和数组array中的最后一个元素；

        (1) 当array[min]+array[max] == sum的时候：

             首先判断是否是第一次遇到满足条件的两个数，是的话将这两个数的乘积保存下来，并且用两个变量分别保存这两个数，目的是为了防止还有满足条件的数。当还有满足条件的数时，再将这两个数的乘积与之前保存满足条件的两个数的乘积做比较，如果比之前的还小，重新保存满足条件的这两个数。

        (2)当array[min]+array[max]  > sum的时候：

                  max -=1;

        (3)当array[min]+array[max]<sum的时候：

                  min +=1;

       最后，如果没有满足条件的数，则直接返回一个空数组，否则，将满足条件的数存到一个数组中进行返回。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int min = 0;
        int max = array.length-1;
        int num1 = 0;
        int num2 = 0;
        int chen = 0;
        ArrayList<Integer> array1 = new ArrayList<Integer>();
        while(min<max){
            if(array[min]+array[max] == sum){
               if(chen == 0){
                  chen = array[min]*array[max];
                  num1 = array[min];
                  num2 = array[max];
               }
               if(array[min]*array[max] < chen){
                   num1 = array[min];
                   num2 = array[max];
               }
                min += 1;
                max -= 1;
            }
            else if(array[min]+array[max] > sum){
                max -= 1;
            }
            else{
                min += 1;
            }
        }
        if(num1 == 0 && num2 == 0){
            return array1;
        }
        array1.add(num1);
        array1.add(num2);
        return array1;
    }
}