LeetCode 18. 四数之和（中）

三数之和的升级版，巧用三指针解决问题。

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意： 答案中不可以包含重复的四元组。

示例

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

考察知识点

多指针、哈希表、双指针

核心思想

本题是三数之和的进阶题目，强烈建议您先看三数之和的 解题思路，看过之后再来看本题目，思路也就非常清晰了。

具体来说，对比三数之和最快的双指针方法，我们只需在外层在嵌套一层循环即可。这样时间复杂度将从 \(O(N^2)\) 变为\(O(N^3)\)。

有没有更快的解法？ 维基百科 中提到了三数之和小于 \(O(N^2)\) 的时间复杂度的解法，因此四数之和的时间复杂度理论上可以小于 \(O(N^3)\)，但是我认为有些“超纲了”，没必要掌握。

我们仍然可以在 \(O(N^3)\) 的时间复杂度内通过增加条件判断使得速度得到很大提升。主要考虑以下几点：

指针依次是 p,k,i,j，如果 nums[p] + 3 * nums[p + 1] > target，因为 nums 按升序排列，所以之后的数肯定都大于 target ，直接 break；

如果 nums[p] + 3 * nums[-1] < target，那么当前的 nums[p] 加其余三个数一定小于 target，故 p 直接下一位即可，continue；

k 和 p 判断完全一样，只是将 3 变成了 2，target 变成了 target - nums[p] - nums[k]。

同样地，为了避免结果重复，某个指针遇到相同的数需要直接跳过，这与三数之和是一样的。

简单来说，就是用两层循环，把四数之和转化成二数之和。这道题目，去重是关键。

LeetCode题解

Python版本

基于题解多指针的版本

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution:
    def fourSum(self, nums: list, target: int) -> list:
        nums.sort()
        n = len(nums)
        res = []
        p = 0  # p, k, i, j
        while p < n - 3:  # 这一层循环是p指针变化
            # p的特判
            if nums[p] + 3 * nums[p + 1] > target: break  # 如果  nums[p] + 3 * nums[p + 1] > target ，因为 nums 按升序排列，所以之后的数肯定都大于 target ，直接 break；
            if nums[p] + 3 * nums[-1] < target:  # 如果 nums[p] + 3 * nums[-1] < target，那么当前的 nums[p] 即使加上最大的 nums[-1]*3 也小于target，那么加其后的三个数一定小于 target，故 p 直接下一位即可，continue；
                while p < n - 4 and nums[p] == nums[p + 1]: p += 1  # 先判断重复，为了避免结果重复，某个指针遇到相同的数需要直接跳过。
                p += 1  # 再移动到下一位
                continue
            k = p + 1
            # k的特判
            while k < n - 2:   # 这一层循环是p指针不变，k指针持续增加。这种写法，实际上就是在three_sum问题的基础上再在外面嵌套一层。
                if nums[p] + nums[k] + 2 * nums[k + 1] > target: break  # 之所以是2 * nums[k + 1] 是因为p k之后还有2个指针i,j对应的数字
                if nums[p] + nums[k] + 2 * nums[-1] < target:  #  nums[k] + 2 * nums[-1] 同上
                    while k < n - 3 and nums[k] == nums[k + 1]:
                        k += 1
                    k += 1
                    continue
                i = k + 1  # 二数之和的左指针
                j = n - 1  # 二数之和的右指针
                new_target = target - nums[p] - nums[k]  # 将四数之和问题转化为二数之和问题
                while i < j:  # 这一层循环时p, k指针不变，将四数之和问题转化为二数之和问题，寻找最优解。
                    _sum =nums[i] + nums[j]
                    if _sum > new_target: j -= 1  # 大于目标值 右指针左移减小
                    elif _sum < new_target: i += 1  # 小于目标值 左指针右移增大
                    else:  # 满足条件
                        res.append([nums[p],nums[k],nums[i],nums[j]])
                        i += 1
                        j -= 1
                        while i < j and nums[i] == nums[i - 1]: i += 1 # 避免i指针 结果重复 与加之前比
                        while i < j and nums[j] == nums[j + 1]: j -= 1 # 避免j指针 结果重复 与减之前比
                while k < n - 3 and nums[k] == nums[k + 1]: k += 1  # 避免k指针 结果重复
                k += 1
            while p < n - 4 and nums[p] == nums[p + 1]: p += 1  # 避免p指针 结果重复
            p += 1
        return res

print("leet code accept!!!")
Input = [
    [1, 0, -1, 0, -2, 2],
    [-1, 0, 1, 2, -1, -4],
    [-3,-2,-1,0,0,1,2,3]
]
Input1 = [0, -1, 0]
Answer = [
    [
        [-1,  0, 0, 1],
        [-2, -1, 1, 2],
        [-2,  0, 0, 2]
    ],
    [
        [-4,0,1,2],
        [-1,-1,0,1]
    ],
    [[-3,-2,2,3],[-3,-1,1,3],[-3,0,0,3],[-3,0,1,2],[-2,-1,0,3],[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.fourSum(Input[i], Input1[i])
        print(result)
        print(Answer[i])

自己复现代码出现问题的地方

注意避免出现同样的错误了

误写

1
2
3
4
5
6
if nums[p] + 2*nums[k+1] > target:  # 这里只加上了三个数字
    break
if nums[p] + 2*nums[-1] < target:   # 这里只加上了三个数字
    while k < n -3 and nums[k] == nums[k+1]: k += 1
    k += 1
    continue

正解

1
2
3
4
5
6
if nums[p] + nums[k] + 2*nums[k+1] > target:  # 实际上应该加上四个数字
    break
if nums[p] + nums[k] + 2*nums[-1] < target:   # 实际上应该加上四个数字
    while k < n -3 and nums[k] == nums[k+1]: k += 1
    k += 1
    continue

误写

1
2
3
4
    p += 1
    while p < n - 4 and nums[p] == nums[p+1]: p += 1

return res

正解

1
2
3
4
5
    while p < n - 4 and nums[p] == nums[p+1]: p += 1  # 应该先去重后自增
    p += 1

return res