NeetCode #201LC-18MediumTwo PointersNC 250
← Back to All Problems#201 · #18 · 4Sum(四数之和)
📌 Problem Statement & Constraints
Given an array
nums and a target, return all unique quadruplets [a, b, c, d] that sum to target. Constraints: 1 <= nums.length <= 200, -10^9 <= nums[i], target <= 10^9.💡 Core Algorithmic Approaches
- Extend the 3Sum template with one more outer loop: sort, fix two indices, then solve a two-sum on the remaining suffix with two pointers.
- Deduplicate at every level: the first fixed index, the second fixed index, and both pointers after a hit.
- Pruning helps a lot: once
nums[i] > targetwith all values non-negative the remaining loop can break, and range checks can skip hopeless pairs. - The overall complexity is O(n^3), which is 8 * 10^6 for n = 200 -- acceptable.
💻 Benchmark Python3 Implementation
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # dedup the first index
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # dedup the second index
l, r = j + 1, n - 1
need = target - nums[i] - nums[j]
while l < r:
s = nums[l] + nums[r]
if s == need:
res.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif s < need:
l += 1
else:
r -= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^3): two nested loops plus an inner two-pointer scan.
💾 Space Complexity
O(1) extra beyond the output and the sort.
⚠️ Interview Pitfalls & Follow-ups
- Deduplicating only at the innermost level: repeated quadruplets would still appear, because the same value can be chosen at the outer levels in different ways.
- Using a hash map for the inner two-sum: it works but reintroduces O(n) space and duplicate handling.
- Forgetting the
j > i + 1guard: the dedup for the second index must not skip the first validj. - Assuming the answer fits in 32 bits: intermediate sums can reach 4 * 10^9, so 64-bit arithmetic is needed in fixed-width languages. Python is safe.
- Trying to prune with
nums[i] > target: that is only valid when all remaining values are non-negative, which the constraints do not guarantee.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Two Pointers Problems
中文速览与面试要点
四数之和
给你一个由 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.length ≤ 200;-10^9 ≤ nums[i] ≤ 10^9;-10^9 ≤ target ≤ 10^9。
核心要点
- 排序 + 两层枚举 + 双指针(标准解) :在三数之和的基础上再加一层循环。外层枚举 a、次层枚举 b,内层用双指针在 b+1..n−1 中找两数之和为 target − nums[a] − nums[b] 。
- 两层都要去重 :a 与它的前一个元素比较,b 与它的前一个元素比较(注意 b 的去重条件是 b > a + 1 ,避免跳过同一 a 下的第一个 b)。
- 内层双指针也要去重 :找到解后跳过相邻重复值。
- 复杂度 :排序 O(n log n) + O(n³) 枚举,n ≤ 200 时约 8 × 10^6 次操作,可接受。
常见陷阱
- 第二层去重写成 b > 0 and nums[b] == nums[b-1] :应为 b > a + 1 。若用 b > 0 ,在 b == a + 1 时会错误地跳过合法解(因为它与 nums[a] 比较而非与同一 a 下的前一个 b 比较)。
- 整数溢出 :nums[i] 与 target 可达 ±10^9,四数之和可达 ±4 × 10^9,超出 32 位 int 范围。Python 无此问题,但 C++/Java 必须用 long long。
- 忘记内层去重 :会产生重复四元组。
- 用四重循环 :O(n⁴) 在 n = 200 时是 1.6 × 10^9,必然超时。
参考实现
class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
res = []
for a in range(n - 3):
if a > 0 and nums[a] == nums[a - 1]:
continue # 第一层去重
for b in range(a + 1, n - 2):
if b > a + 1 and nums[b] == nums[b - 1]:
continue # 第二层去重
l, r = b + 1, n - 1
need = target - nums[a] - nums[b]
while l < r:
s = nums[l] + nums[r]
if s == need:
res.append([nums[a], nums[b], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1 # 内层去重(左)
while l < r and nums[r] == nums[r + 1]:
r -= 1 # 内层去重(右)
elif s < need:
l += 1
else:
r -= 1
return res