How do I ensure uniqueness in the 4Sum solution?

Uniqueness is maintained by sorting the array first, then skipping over duplicate elements during the two-pointer scan, both in the outer loop and inner iteration.

What is the time complexity of the 4Sum problem?

The time complexity is O(n^3) due to the triple nested iteration over the array and the two-pointer scanning, which combined leads to cubic complexity.

Why is sorting necessary in the 4Sum solution?

Sorting the array allows the efficient application of the two-pointer technique to find valid quadruplets and helps in skipping duplicates effectively during the scan.

What edge cases should I consider in 4Sum?

Consider edge cases like an array with fewer than four elements, arrays with only one repeated value, and cases where no valid quadruplet exists.

Can this approach be used for other variations like 3Sum?

Yes, the same two-pointer scanning technique can be applied to variations like 3Sum, where you reduce the target sum by removing one element.

#18

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）： 0 a 、 b 、 c 和 d 互不相同 n…

数组双指针排序

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

lightbulb

解题思路

方法一：排序 + 双指针

我们注意到，题目中要求找到不重复的四元组，那么我们可以先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举四元组的前两个元素 $nums[i]$ 和 $nums[j]$ ，其中 $i \lt j$ ，在枚举的过程中，我们跳过重复的 $nums[i]$ 和 $nums[j]$ 。然后，我们用两个指针 $k$ 和 $l$ 分别指向 $nums[i]$ 和 $nums[j]$ 后面的两端，令 $x = nums[i] + nums[j] + nums[k] + nums[l]$ ，我们将 $x$ 与 $target$ 比较，进行如下操作：

如果 $x \lt target$ ，则更新 $k = k + 1$ 以得到更大的 $x$ ；
如果 $x \gt target$ ，则更新 $l = l - 1$ 以得到更小的 $x$ ；
否则，说明找到了一个四元组 $(nums[i], nums[j], nums[k], nums[l])$ ，将其加入答案，然后我们更新指针 $k$ 和 $l$ ，并跳过所有重复的元素，防止答案中包含重复的四元组，继续寻找下一个四元组。

时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(\log n)$ ，其中 $n$ 是数组的长度。

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

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        ans = []
        if n < 4:
            return ans
        nums.sort()
        for i in range(n - 3):
            if i and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                k, l = j + 1, n - 1
                while k < l:
                    x = nums[i] + nums[j] + nums[k] + nums[l]
                    if x < target:
                        k += 1
                    elif x > target:
                        l -= 1
                    else:
                        ans.append([nums[i], nums[j], nums[k], nums[l]])
                        k, l = k + 1, l - 1
                        while k < l and nums[k] == nums[k - 1]:
                            k += 1
                        while k < l and nums[l] == nums[l + 1]:
                            l -= 1
        return ans

speed

复杂度分析

指标	值
时间	O(n^{k - 1})
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to handle duplicates effectively while using the two-pointer technique?
question_mark
Can you explain why sorting is a crucial step in this problem?
question_mark
Will you ensure that the final result contains only unique quadruplets without redundancy?

warning

常见陷阱

外企场景

error
Skipping duplicate values: If duplicates are not skipped properly, the algorithm will return repeated quadruplets.
error
Incorrect pointer movement: Failing to advance the pointers past duplicates after finding a valid quadruplet leads to inefficiency and incorrect results.
error
Overlooking edge cases: Ensure to handle cases where no quadruplet exists or when the array length is smaller than 4.

swap_horiz

进阶变体

外企场景

arrow_right_alt
3Sum: A similar problem, but instead of quadruplets, you find all unique triplets in an array that sum to a target.
arrow_right_alt
5Sum: This extends the 4Sum problem by finding all unique quintuplets that sum to the target value.
arrow_right_alt
Sum of Three Largest/Smallest: Variants where the goal is to find the sum of the three largest or smallest numbers in the array that sum to the target.

help

常见问题

外企场景

继续练习

#16 最接近的三数之和 #15 三数之和 #75 颜色分类