数组中找2个数之和为target

题目

数组中找到所有的和为target的整数对
例如：数组 [1,8,7,4,4,5,2,4,10,0]，target为8
结果为：(0，8)(1，7)(4，4)
因为：0+8=8，1+7=8，4+4=8

解题思路

1. 数组nums[]按照升序排序
2. 定义两个下标，i指向第一个元素，j指向最后一个元素
3. 求和当前两个数组元素(nums[i] + nums[j])，并且与target相比较
   3.1. 如果nums[i] + nums[j]等于target，记录下来当前两个数。i加1(向右移动一位)，如果新的nums[i]与旧的nums[i]值相同，继续加1，直到不相同为止，且i不可以超过j，这么做是为了过滤掉重复的数字对；j与i正好相反，j减1(向左移动一位)，如果新的nums[j]与旧的nums[j]相等，继续j减1，直到不相等且j不可以小于i。
   3.2. 如果nums[i] + nums[j]大于target，也就是nums[i] + nums[j]这两个值之和需要减小，那么在升序的数组中，后面的坐标j就需要向左移动，j自减1。
   3.3. 如果nums[i] + nums[j]小于target，也就是nums[i] + nums[j]这两个值之和需要增加，i自增1。
4. 持续上面第3步的操作，直到遍历完整个数组，得到所有的数字对。

上面的算法，假设数组长度为n，时间复杂度就是O(n)，因为只遍历了一次数组。

在这道题中比较容易想到的，并且符合直觉的想法就是两次循环遍历数组，把数组的每一个元素都与数组其他元素加和比较，找到最终结果，此时时间复杂度O(n*n)。而关于上面的算法，比较有疑问的地方就是i和j同时移动会不会漏掉一些数据对呢？

证明上面时间复杂度O(n)的算法可行

如果完整的证明需要使用数学归纳法，这里用不太标准，但是容易理解的方法证明上面的算法。
已知数组nums[]升序，两个下标，前面的下标为i，后面的下标为j，目标值为target。
现在假设nums[i] + nums[j] > target，
按照算法此时应该执行j--，如果错过了某个符合结果的数据对，那么这个数据对只可能在0-i的区间，因为大于i区间，nums[i] + nums[j]的和只会更大。
而nums[0]与nums[i]之间的元素已经被遍历过了，遍历的时候，是在j更大，nums[i] + nums[j]小于target的情况下，i加1。所以nums[0]与nums[i]之间的元素与当前的下标j对应的nums[j]求和，只会更小于target。所以在nums[i] + nums[j] > target时，执行j--，移动j不会错过数据对。
同样地，另外两种情况nums[i] + nums[j]小于和等于target的情况，推导过程与大于相反。

代码

细节在代码中已经注释，main方法用于测试结果，也写在类中了。

public class TwoSum {
    public Map<Integer, Integer> twoSum(int[] nums, int target) {
        //结果存储在map，存在map中可以不滤重，因为map的key是唯一的
        Map<Integer, Integer> map = new HashMap<>();
        if (null == nums || nums.length < 2){
            return map;
        }
        //JDK自带的排序函数对数组进行排序
        Arrays.sort(nums);
        //定义两个数组下标
        int i = 0, j = nums.length - 1;
        while (i < j){
            //如果数组两个元素之和等于target
            if (nums[i] + nums[j] == target){
                //保存结果
                map.put(nums[i], nums[j]);
                //i自增1，并且判断是否是重复数字元素
                i++;
                while (i < j && nums[i] == nums[i - 1]){
                    i++;
                }
                //j自减1，并且判断是否是重复数字元素
                j--;
                while (i < j && nums[j] == nums[j + 1]){
                    j--;
                }
            }else if (nums[i] + nums[j] > target){//数组两个元素之和大于target
                j--;
            }else {//数组两个元素之和小于target
                i++;
            }
        }
        return map;
    }

    public static void main(String[] args){
        int[] array = {1,8,7,4,4,5,2,4,10,0};
        int target = 8;
        TwoSum sum = new TwoSum();
        Map<Integer, Integer> map = sum.twoSum(array, target);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            System.out.println(entry.getKey() + "+" + entry.getValue() + "=" + target);
        }
    }
}