42：和为S的两个数字

题目描述

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

返回值描述:

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

第一种解法

双层for循环遍历保存最小的呗

    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> result = new ArrayList<>();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(result.size()==0){result.add(0,array[i]);result.add(1,array[j]);}else if(result.size()==2){if(array[i]*array[j]<result.get(0)*result.get(1)){result.add(0,array[i]);result.add(1,array[j]);}}}}}return result;}

第二种解法

最外层乘积最小，效率低于上面

    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> result=new ArrayList<Integer>();//边界条件if(array==null||array.length<=1){return result;}int smallIndex=0;int bigIndex=array.length-1;while(smallIndex<bigIndex){//如果相等就放进去if((array[smallIndex]+array[bigIndex])==sum){result.add(array[smallIndex]);result.add(array[bigIndex]);//最外层的乘积最小，别被题目误导break;}else if((array[smallIndex]+array[bigIndex])<sum){smallIndex++;}else{bigIndex--;}}return result;
}

第三种解法：双指针法

对于有序数组一般双指针法，跟上面上不多了

 public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> res= new ArrayList<>();int i = 0,j=array.length-1;int ij=Integer.MAX_VALUE;while(i<j){int sumV = array[i]+array[j];if(sumV>sum){j--;}else if(sumV<sum){i++;}else{if(ij>i*j){res.clear();res.add(array[i]);res.add(array[j]);ij=i*j;}i++;}}return res;}

第四种解法

利用Hashmap存储

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {HashMap<Integer,Integer> map = new HashMap<>();ArrayList<Integer> list = new ArrayList();int temp = Integer.MAX_VALUE;for(int i=0; i<array.length; i++){map.put(i,array[i]);}Set<Map.Entry<Integer, Integer>> entry = map.entrySet();for(Map.Entry<Integer, Integer> en: entry){if(map.containsValue((sum-en.getValue())) && (sum-en.getValue())*en.getValue()<temp){list.clear();temp = (sum-en.getValue())*en.getValue();list.add(en.getValue());list.add(sum-en.getValue());}}Collections.sort(list);return list;}