LeetCode N数之和

1-两数之和

梦开始的地方 （LeetCode 第一题）

传送门

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

这题的暴力解法是遍历所有可能的组合，时间复杂度为 $O(N^2)$

暴力解法的本质是：先确定一个数，看是否能找到另一个数，使它们的组合可以满足题意。这里的「找到」启发我们可以使用查找表，在 java 中即 Set/Map。

直接按照这个思路，可以写出下面的代码：

1. 遍历所有元素存入查找表。
2. 再次遍历所有元素 n，查询表中是否存在元素 target-n

如此一来，时间复杂度可以降低到 $O(N)$，但依然要遍历两遍数组。其实可以只遍历一遍。我们遍历时查询 target-n 是否在表中，若不在则把 n 存入查找表。假设元素 a+b=target，当遍历到 a 时，显然 b=target-a 不在，把 a 加入集合，未来一定会遍历到 b，此时 target-b=a 已经存在了，顺利得到答案。因此没有必要特地事先遍历一遍来构建查找表，完全可以一边遍历一边查找一边构建。

之所以可以这么做，核心原因是我们要找的两个数是「对称」的并且存在于同一个数组中。即：通过 a 可以计算出 b，通过 b 也可以计算出 a；并且 a,b 都会被遍历到。

代码（java）：

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>(nums.length); // v->i
    for (int i = 0; i < nums.length; i++) {
      int temp = target - nums[i];
      if (map.containsKey(temp))
        return new int[]{map.get(temp), i};
      map.put(nums[i], i);
    }
    throw new IllegalArgumentException();
  }
}

454-四数之和 II

传送门

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

这道题如果暴力求解，时间复杂度是 $O(N^4)$，不可接受。借助上一题的思路，可以先确定三个数，把它们之和视为 a，然后在最后一个数组中查找是否存在第四个数视为 b=-a。这样时间复杂度降低为 $O(N^3)$，好一点了，但不够好。

在这个解法中，需要事先遍历 num4 建立查找表。因为此时的 a 与 b 虽然对称，但不在同一个数组中。

换一个思路，我们可以把 4 个数组分为两部分，前两个之和为 a，后两个之和为 b。对 a 或 b 建立查找表，遍历另一个，在查找表中寻找配对。这样时间复杂度可以降低到 $2N^2$，即 $O(N^2)$.

遍历前两个数组的所有组合并建立查找表耗费 $N^2$，遍历后两个数组的所有组合（同时查询表）耗费 $N^2$，故总共耗费 $2N^2$。

代码（java）：

class Solution {
  public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> map = new HashMap<>(); // num1+num2 -> count
    for (int n1 : nums1)
      for (int n2 : nums2) {
        int sum = n1 + n2;
        if (map.containsKey(sum))
          map.put(sum, map.get(sum) + 1);
        else
          map.put(sum, 1);
      }
    int result = 0;
    for (int n3 : nums3)
      for (int n4 : nums4) {
        if (map.containsKey(-n3 - n4))
          result += map.get(-n3 - n4);
      }
    return result;
  }
}

这里有个细节，建立查找表时不能用 Set 因为可能不同的元素组合得到相同的值，需要记录组合的个数。

15-三数之和

传送门

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

这道题猛一看和第一题差不多：在同一个数组中寻找 N 个元素。但有两个不起眼却影响巨大的差异：①第一题要求我们返回下标，这一题要求返回数值。②第一题只有一个解，这题有多个。

查找表法

如法炮制，我们选定一个数 a，将 -a 视为 target，这样就回到了第一题：在数组中选出两个数 b/c，使得 b+c=-a。

具体做法是：遍历数组，依次尝试将每一个元素作为 a，遍历之后其余的元素，对于每一个元素 b，查询 -a-b 是否在表中，若不在则把 b 放入查找表，否则 (a, b, -a-b) 是一个解。

这个做法有两个问题：

1. 我们的算法可以自然地确保返回的下标组合不重复，但不能保证这些不同的下标它们实际的值不同。
2. 对于固定的 a，可能有多个 [b,c] 组合。这个问题可通过查到表时只记录不停止查找来解决。

至于第一个问题，也不是无解，但会比较麻烦也容易出错。

双指针法

我们对于双指针法并陌生，这个方法要求数组有序，这样才可以确定哪个指针应该往那个方向移动。与查找表法相比，双指针法也需要先确定一个 a，只是对于剩下两个元素的选择，稍有不同。

1. 把数组排序，例如 小->大。
2. 遍历数组，依次将每一个元素视为 a（忽略重复的元素）
3. 定义指针 pb 指向 a 的下一个元素，pc 指向末尾。
4. 若 a+b+c<0，则右移 pb；若 a+b+c>0，则左移 pc；若 a+b+c=0，则记录一个解，统一向中间移动两个指针。pb,pc 移动过程中注意去重。

时间复杂度为 $O(N^2)$。有一个小优化，若 a>0 那么就不需要查找了，后面全部大于 0，其和不可能为 0。

具体写法有两个陷阱：

1. 去重 a 时，应该向前去重而不是向后去重。例如 -1,-1,2 这种情况，一个解是 a=-1,b=-1,c=2，若是向后去重，a 直接跳过了第一个 -1 ，b 只能为 2 从而遗漏这个解。只有确定 a=-1 无解时，才可以跳过后续 a=-1 的情况（因为后续 b,c 的可选项一定比第一次少，若第一次无解，后续一定无解）。
2. 同理，b,c 也应该向两边去重，同时去重逻辑一定要注意边界，不要把 a 的值也视为重复。否则对于输入 nums=0,0,0，a=nums[0]，b 会因为向前去重而漏解。

代码（java）：

class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    // 双指针写法
    List<List<Integer>> result = new LinkedList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
      int a = nums[i];
      // 若第一个元素大于0，后面元素必定大于0，其和不可能为0
      if (a > 0) return result;
      if (i > 0 && nums[i] == nums[i - 1])
        continue; // a 去重
      int l = i + 1, r = nums.length - 1;
      while (l < r) {
        if (l - 1 > i && nums[l] == nums[l - 1]) {
          l++;
          continue; // b 去重
        }
        if (r + 1 < nums.length && nums[r] == nums[r + 1]) {
          r--;
          continue; // c 去重
        }
        if (a + nums[l] + nums[r] > 0) {
          r--;
        } else if (a + nums[l] + nums[r] < 0) {
          l++;
        } else {
          result.add(Arrays.asList(a, nums[l], nums[r]));
          l++;
          r--;
        }
      }
    }
    return result;
  }
}

18-四数之和

传送门

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

本题和第二题 454 不同，和第三题 15 类似：要找的元素在同一个数组中，返回元素值而不是下标，不能重复。

按照第三题的思想，这题我们用两层循环确定 a,b 的值，然后用双指针确定剩下 c,d 的值。时间复杂度为 $O(N^3)$。

这里不能仿照第三题优化 if(a > target) break;，因为 a,target 可能都是负数，后面虽然比 a 大但依然可能是负数，它们累加可能 sum 可能变小。但我们可以针对性地调整一下优化算法：if(a>target && a>=0) break;

需要注意的是 LeetCode 更新了一个用例，会导致 java int 越界：

[1000000000,1000000000,1000000000,1000000000]
-294967296

因此计算和的时候注意强制转换为 long。

代码（java）：

class Solution {
  public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new LinkedList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
      if (i > 0 && nums[i - 1] == nums[i]) continue; // a 去重
      int a = nums[i];
      if (a > target && a >= 0) break; // 优化
      for (int j = i + 1; j < nums.length; j++) {
        if (j > i + 1 && nums[j - 1] == nums[j]) continue; // b 去重
        int b = nums[j];
        if (a + b > target && a + b >= 0) break; // 优化
        int l = j + 1;
        int r = nums.length - 1;
        while (l < r) {
          if (l > j + 1 && nums[l - 1] == nums[l]) {
            l++;
            continue; // c 去重
          }
          if (r < nums.length - 2 && nums[r + 1] == nums[r]) {
            r--;
            continue; // d 去重
          }
          long sum = (long) a + b + nums[l] + nums[r];
          if (sum < target) {
            l++;
          } else if (sum > target) {
            r--;
          } else {
            result.add(Arrays.asList(a, b, nums[l], nums[r]));
            l++;
            r--;
          }
        }
      }
    }
    return result;
  }
}