18. 4Sum¶
Edited by Charles
Medium · Python · HashTable
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
Pay attention to below points:
target in this question can be any number, instead of 0 in 15. 3Sum based on 15. 3Sum, we need one more iteration for the fourth number.
Original study notes follow, including intermediate snippets and earlier attempts.
Pay attention to below points:
- target in this question can be any number, instead of 0 in 15. 3Sum
- based on 15. 3Sum, we need one more iteration for the fourth number.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n):
if i > 0 and nums[i - 1] == nums[i]:
continue
triples = self.threeSum(nums, i + 1, target - nums[i])
for triple in triples:
triple.append(nums[i])
result.append(triple)
return result
def threeSum(self, nums, start, target):
n = len(nums)
result = []
for i in range(start, n):
if target >= 0 and nums[i] > target:
break
if i > start and nums[i] == nums[i - 1]:
continue
left = i + 1
right = n - 1
while left < right:
sum3 = nums[i] + nums[left] + nums[right]
if sum3 > target:
right -= 1
elif sum3 < target:
left += 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[right - 1] == nums[right]:
right -= 1
while left < right and nums[left] == nums[left + 1]:
left += 1
left += 1
right -= 1
return result
Claude 优化版¶
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | January 5, 2026 |
Python solution¶
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n - 3):
if i > 0 and nums[i - 1] == nums[i]:
continue
# 最小的4数和已经 > target，后面只会更大，直接结束
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
break
# 当前i配上最大的3个数都 < target，这个i凑不出来，跳过
if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
continue
for t in self.threeSum(nums, i + 1, n, target - nums[i]):
t.append(nums[i])
result.append(t)
return result
def threeSum(self, nums, start, n, target):
result = []
for i in range(start, n - 2):
if i > start and nums[i - 1] == nums[i]:
continue
if nums[i] + nums[i+1] + nums[i+2] > target:
break
if nums[i] + nums[n-1] + nums[n-2] < target:
continue
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s > target:
right -= 1
elif s < target:
left += 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[right-1] == nums[right]:
right -= 1
while left < right and nums[left] == nums[left+1]:
left += 1
left += 1
right -= 1
return result