1. 两数之和

该题要求返回下标，且至多有一对数和为target，不存在重复问题

  1.     public int[] twoSum(int[] nums, int target) {
  2.         Map<Integer, Integer> hm = new HashMap<>();
  3.         for(int i = 0; i < nums.length; ++i){
  4.             if (hm.containsKey(target - nums[i])){
  5.                 return new int[]{i, hm.get(target - nums[i])};
  6.             }else{
  7.                 hm.put(nums[i], i);
  8.             }
  9.         }
  10.         return new int[0];
  11.     }

167. 两数之和 II - 输入有序数组

该题要求必须使用常量级的额外空间，且是非递减数列，那说明，排好序了，直接双指针完事了

15. 三数之和

该题要求，不能包含重复的三元组，当用两层循环计算得到a+b的值，在看哈希表里是否有0-a-b，但是这样会包含重复三元组，去重会非常的麻烦
思考：两数之和，可不可以使用双指针呢？由于两数之和问题返回的是下标，而双指针解法一定要排序，排序了下标就变了，如果要返回数值，则可以使用

  1.     public List<List<Integer>> threeSum(int[] nums) {
  2.         List<List<Integer>> ans = new ArrayList<>();
  3.         Arrays.sort(nums);
  5.         //找出a + b + c = 0
  6.         //a = nums[i], b = nums[left], c = nums[right]
  7.         for (int i = 0; i < nums.length; ++i){
  9.             //必须有正有负才能使结果为0
  10.             if ( nums[i] > 0)
  11.                 return ans;
  13.             //去重
  14.             //如果没有i>0这个条件，即nums[i] == nums[i + 1]， 会产生什么影响？ [-1, -1, 2]
  15.             //因此应该判断是否与之前一样，因为之前的结果已经算出来了
  16.             if ( i > 0 && nums[i] == nums[i-1])
  17.                 continue;
  19.             int left = i + 1;
  20.             int right = nums.length - 1;
  22.             while(left < right){
  23.                 // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
  24.                 //while (right > left && nums[right] == nums[right - 1]) right--;
  25.                 //while (right > left && nums[left] == nums[left + 1]) left++;
  27.                 if ( nums[i] + nums[left] + nums[right] > 0){
  28.                     right --;
  29.                 }else if ( nums[i] + nums[left] + nums[right] < 0){
  30.                     left ++;
  31.                 }else{
  32.                     ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
  34.                     //再次去重，左右分别去重
  35.                     while (right > left && nums[right] == nums[right - 1])
  36.                         right--;
  37.                     while (right > left && nums[left] == nums[left + 1])
  38.                         left++;
  40.                     right --;
  41.                     left ++;
  42.                 }
  43.             }
  44.         }
  45.         return ans;
  46.     }

16. 最接近的三数之和

个人思路

同三数之和，只是不用去重，其实仍可以去重，降低时间消耗，但是这里去重的细节跟三数之和稍微不同

  1. class Solution {
  2.     public int threeSumClosest(int[] nums, int target) {
  3.         int ans = nums[0] + nums[1] + nums[2];
  4.         Arrays.sort(nums);
  6.         for(int i = 0; i < nums.length; ++i){
  7.             //去重
  8.             if( i > 0 && nums[i] == nums[i-1])
  9.                 continue;
  11.             int left = i+1;
  12.             int right = nums.length - 1;
  13.             int temp = 0;
  14.             while(left < right){
  15.                 temp = Math.abs(target - nums[i] - nums[left] - nums[right]);
  16.                 ans = temp < Math.abs(ans - target) ? nums[i]+nums[left]+nums[right] : ans;
  17.                 if(nums[i]+nums[left]+nums[right] > target){
  18.                     //right --; 注意这里的去重操作，应该夹在哪里，但是无论如何，都应该有两个right--，left省略了
  19.                     while( right > left && nums[right] == nums[right - 1])
  20.                         right--;
  21.                     right --;
  22.                 }else if(nums[i]+nums[left]+nums[right] < target){
  23.                     left++;
  24.                 }else{
  25.                     return target;
  26.                 }
  27.             }
  28.         }
  29.         return ans;
  30.     }
  31. }

18. 四数之和

解法同三数之和，不过是在外面再加一层循环

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if ( nums==null || nums.length < 4)
            return ans;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; ++i){
            if ( i > 0 && nums[i] == nums[i-1])
                continue;
            for (int j = i + 1; j < nums.length; ++j){
                if (j > i + 1 && nums[j] == nums[j-1])
                    continue;
                int left = j+1;
                int right = nums.length-1;
                while (left<right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target){
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        ans.add(Arrays.asList(nums[i] , nums[j] , nums[left] , nums[right]));
                        while (left < right && nums[right]==nums[right-1]) right--;
                        while (left < right && nums[left] == nums[left+1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return ans;
    }

454. 四数相加 II

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //暴力方法是四层遍历，时间复杂度为n^4
        //如果先遍历第一个数组，在便利另外三个是n^3
        //所以最低时间复杂度就是两两组合吗？
        Map<Integer, Integer> map = new HashMap<>();
        int temp = 0;
        int res = 0;
        for (int i : nums1){
            for (int j : nums2){
                temp = i + j;
                map.put(temp, map.getOrDefault(temp, 0)+1);
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                temp = i + j;
                if (map.containsKey(-temp)){
                    //res++; //不是++，两个元素之和可能有重复
                    res += map.get(-temp);
                }
            }
        }
        return res;
    }