应用题-双指针-四数之和 （ 两数之和 三数之和 通用做法 ）
- 版权声明：本站原创文章，于2026-04-24，由 管理员 发表。
- 转载请注明： 应用题-双指针-四数之和 （ 两数之和 三数之和 通用做法 ） | CodeGarden
```python
class Solution:
# 一个由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
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len( nums )
nums.sort()
# 三数之和的基础上增加一层循环
ans = []
for i in range( n ):
# 去重
if i > 0 and nums[ i ] == nums[ i - 1 ]: continue
for j in range( i + 1, n ):
# 去重
if j > i + 1 and nums[ j ] == nums[ j - 1 ]: continue
a = nums[ i ]
b = nums[ j ]
# 确定c和d
k = j + 1
h = n - 1
while k < h:
c = nums[ k ]
d = nums[ h ]
if a + b + c + d > target: h -= 1
elif a + b + c + d < target: k += 1
else:
ans.append( [ a, b, c, d ] )
# 去重
while k < h and nums[ k + 1 ] == c: k += 1
while k < h and nums[ h - 1 ] == d: h -= 1
k += 1
h -= 1
return ans
```
**增加剪枝**
```python
class Solution:
# 一个由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
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len( nums )
nums.sort()
# 三数之和的基础上增加一层循环
ans = []
for i in range( n ):
# 剪枝
if nums[ i ] > target and nums[ i ] >= 0: break
# 去重
if i > 0 and nums[ i ] == nums[ i - 1 ]: continue
for j in range( i + 1, n ):
# 剪枝
if nums[ i ] + nums[ j ] > target and nums[ i ] + nums[ j ] >= 0: break
# 去重
if j > i + 1 and nums[ j ] == nums[ j - 1 ]: continue
a = nums[ i ]
b = nums[ j ]
# 确定c和d
k = j + 1
h = n - 1
while k < h:
c = nums[ k ]
d = nums[ h ]
if a + b + c + d > target: h -= 1
elif a + b + c + d < target: k += 1
else:
ans.append( [ a, b, c, d ] )
# 去重
while k < h and nums[ k + 1 ] == c: k += 1
while k < h and nums[ h - 1 ] == d: h -= 1
k += 1
h -= 1
return ans
```