import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
         ArrayList<Integer> temp_end = new ArrayList<Integer>();
        if(array==null || array.length<2)return temp_end;
        int low=0,high=array.length-1;
        int temp=999999,min=0,max=0;
        /*暴力法
        for(int i=0;i<array.length-1;i++){
            for(int j=i+1;j<array.length;j++){
               if(array[i]+array[j]==sum){
                   if(array[i]*array[j]<temp){
                       min=array[i];
                       max=array[j];
                       temp = array[i]*array[j];
                   }
               }
            }
        }
        if(min!=max){
            temp_end.add(min);
            temp_end.add(max);
            return temp_end;
        }
        return temp_end;
        */
        //双指针法距离越远，乘积越小
        while(low<high){
            int total=array[low]+array[high];
            if(total==sum){
                temp_end.add(array[low]);
                temp_end.add(array[high]);
                break;
            }
            else if(total>sum){
                high--;
            }else
                low++;
        }
        return temp_end;
   }
}