面试题41. 和为s的两个数字

面试题41. 和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使他们的和正好是S。如果有多对数字的和等于S，输出两个数的乘积最小的。
比如，【2, 7, 11, 15】，S = 9，因为2 +7 = ，所以返回2和7

思路1：

如果不考虑乘积最小，可以参考Two Sum问题用一个HashMap做辅助
以【2，7，11，15】 S=9为例。从2开始扫描整个数组，差值9-2=7，此时7 不在HashMap中，就把2和7添加到HashMap中。此时HashMap中的元素为【(2,7)】。

下一步扫描到7，差值9-7=2，发现2已经在HashMap中，就直接返回2和7。
整个算法的时间复杂度为O(n)，就是扫描一遍数组的时间。

参考Two Sum http://blog.csdn.net/u010429424/article/details/77648989

思路2：

由于输入是排序后的数组，数字从小到大递增，所以可以设置两个指针。从两边向中间移动。

比如有一个数组：arr = 【2、7、11、15】，设置两个指针i、j。
初始时，i = 0，j = arr.length-1，其中 i 只能从左边向右边移动，j只能从右边向左边移动，i、j每次只能移动一步。

• 如果arr[i] + arr[j] > S，说明当前的和太小了，应当减小 j，使和变小
• 如果arr[i] + arr[j] < S，说明当前的和太小了，应该增加 i，使和变大

上述思路对应的代码如下：

import java.util.ArrayList;

public class Solution {

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