[LC 1/15/16/18] K-Sum

发表于 | 分类于 ，

本篇将「求和问题」梳理一遍。求和问题是指一类从数组中找出 K 个数满足其和为给定整数的问题。

1 Two Sum

Two Sum - LeetCode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

数组无序

如果使用 Brute-Force 方法，时间复杂度是 $O(n^2)$。

时间复杂度和看空间复杂度均为 $O(n)$ 的方法是建立一个 Hash Table。对于数组中的每一个元素 x，如果对应的 target - x 在 Hash Table 中，则组成符合条件的一对整数。

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] numbers, int target) {
   Map<Integer, Integer> map = new HashMap<>();
   for (int i = 0; i < numbers.length; i++) {
      int x = numbers[i];
      if (map.containsKey(target - x)) {
         return new int[]{ map.get(target - x) + 1, i + 1 };
      }
      map.put(x, i);
   }
   throw new IllegalArgumentException("No two sum solution");
}

数组有序

二分查找

二分查找法在查找 target - x 时应用二分查找，可以将 Hash Table 方法的 $O(n)$ 空间复杂度降为 $O(1)$，但时间复杂度上升——$O(n \log{n})$ runtime, $O(1)$ space。该方法不是最优方法。

双指针

数组已经升序排列。假定在某一时刻，左右两个指针分别指向 A[i] 和 A[j]，那么两者之和有以下三种情况：

  • A[i] + A[j] > target：需要将 j 左移以使 A[i] + A[j] 减小；
  • A[i] + A[j] < target：需要将 i 右移以使 A[i] + A[j] 增大；
  • A[i] + A[j] == target：即为答案，将 i 和 j 同时移动。

可以证明不存在其他情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSum(int[] numbers, int target) {
   // Assume input is already sorted.
   int i = 0, j = numbers.length - 1;
   while (i < j) {
      int sum = numbers[i] + numbers[j];
      if (sum < target) {
         i++;
      } else if (sum > target) {
        j--;
      }
      else {
        return new int[]{ i + 1, j + 1 };
      }
    }
    throw new IllegalArgumentException("No two sum solution");
}

2 3-Sum

3Sum - LeetCode

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

可以将求解 2-Sum 问题的方法应用于求解 3-Sum。由于本题简化了一步，即设定 target = 0，因此从（已排序的）数组中挑一个数 x，只需在剩下的 $n-1$ 个数中找出所有和为 0 - x 两个数即可（可能有多组）。

应用 2-Sum 解法需要额外考虑一点就是重复结果的问题。题目要求返回的集合不能包括重复的「三元组」。因此，在外围循环中遍历每一个元素 A[i] 时，只需在 i 以后的数组上应用 2-Sum 方法，即表示左边指针位置的 low = i + 1。

此外，对形如 [-4, -1, -1, 0, 1, 2] 的数组，当迭代到第二个 -1 时，可以直接跳过，因为（如果执行检索将会）得出的结果已经包含在计算第一个 -1 时得到的结果集中了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>();
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

3 3-Sum Closest

3Sum Closest - LeetCode

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

只需对上述 3-Sum 解法略作修改，在指针移动时对三者之和进行判断即可。时间复杂度是 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int n = nums.length;
    int res = 0;
    if (n <= 3) {
        for (int num:nums)
            res += num;
        return res;
    }

    res = nums[0] + nums[1] + nums[2];
    for (int i = 0; i <= n - 3; i++) {
        int j = i + 1;
        int k = n - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (Math.abs(target - res) >= Math.abs(target - sum)) {
                res = sum;
                if (res == target) return res;
            }
            if (sum > target) k--;
            else if (sum < target) j++;
        }
    }
    return res;
}

4 4-Sum

4Sum - LeetCode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.

1
2
3
4
5
6
7
8
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

类似地，借助 2-Sum 和 3-Sum 可以解决 4-Sum 问题。简单来讲，依然是遍历有序数组元素 A[i] 时，对 A[i+1, n-1] 应用 3-Sum 算法。

LeetCode 讨论板块上的帖子 7ms java code win over 100% - LeetCode Discuss 给出了一种效率极高的方法。其中跳过了许多不可能满足条件的情况，避免了不需要的计算。例如

  1. i > 0 && z == A[i - 1] 时，跳过检查；
  2. A[i] + 3 * A[n - 1] < target 时，i 太小以至于不可能在剩余数组中找出满足条件的三元组；
  3. 4 * A[i] > target 时，i 太大；
  4. 4 * A[i] == target 时，只有当「从 A[i] 开始连续4项均相等」时才满足，其他情况不可能；

除上述以外的其他情况，都执行检查。

具体代码参考帖子。