剑指Offer 042和为S的两个数字

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

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

方法一：双指针法 思路：因为是要求两个数乘积最小的，我们可知肯定是左右两边相差越远的乘积最小，所以用双指针放在数组头部和尾部，求得两者加起来等于S即可输出 代码：

public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) { int i=0,j=array.length-1; if(array==null||array.length==0) return new ArrayList<>(); while(i<j){ if(array[i]+array[j]==sum){ return new ArrayList<>(Arrays.asList(array[i],array[j])); }else if(array[i]+array[j]<sum){ i++; }else{ j--; } } return new ArrayList<>(); }

方法二：HashMap计数法 思路：可以用Map<array[i],S-array[i]>来记，如果找不到该值对应的value值，就放入，找到就用list记下来，最后比较，稍微复杂点

代码：

public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) { Map<Integer,Integer> map = new HashMap<>(); List<Integer> list1 = new LinkedList<>(); List<Integer> list2 = new LinkedList<>(); for (int i = 0; i <array.length ; i++) { if(map.containsValue(array[i])){ list1.add(sum-array[i]); list2.add(array[i]); }else{ map.put(array[i],sum-array[i]); } } if(list1.size()==0){ return new ArrayList<>(); }else{ int i=0,min=Integer.MAX_VALUE; for (int j = 0; j <list1.size() ; j++){ int num=list1.get(j)*list2.get(j); if(min>num){ min=num; i=j; } } return new ArrayList<>(Arrays.asList(list1.get(i),list2.get(i))); } }