元宝 LeetCode 18. 四数之和 Python3实现

LeetCode 18. 四数之和 — Python3 实现

题目描述

给你一个由
“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”

示例：

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

解题思路：排序 + 双指针

核心思想：四数之和 → 固定两个数 + 两数之和（双指针）

1. 排序数组
2. 两层循环固定前两个数
   “i” 和
   “j”
3. 用双指针
   “left” 和
   “right” 在剩余区间找两数之和
4. 去重：跳过重复的枚举值

Python3 代码

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): # 去重：跳过相同的 nums[i] if i > 0 and nums[i] == nums[i - 1]: continue # 剪枝：最小的四个数之和 > target，后面更大，直接 break if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target: break # 剪枝：当前数 + 最大的三个数之和 < target，跳过 if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target: continue for j in range(i + 1, n - 2): # 去重：跳过相同的 nums[j] if j > i + 1 and nums[j] == nums[j - 1]: continue # 剪枝：最小的两数之和 > 剩余 target if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target: break # 剪枝：当前两数 + 最大两数 < target，跳过 if nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target: continue # 双指针查找剩余两数 left, right = j + 1, n - 1 while left < right: total = nums[i] + nums[j] + nums[left] + nums[right] if total == target: result.append([nums[i], nums[j], nums[left], nums[right]]) # 去重：移动指针跳过相同值 while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 elif total < target: left += 1 else: right -= 1 return result

图解流程

以
“nums = [1,0,-1,0,-2,2]”,
“target = 0” 为例：

排序后: [-2, -1, 0, 0, 1, 2]

i=0, nums[i]=-2:
j=1, nums[j]=-1:
双指针 left=2, right=5 → sum = -2-1+0+2 = -1 < 0 → left++
left=3, right=5 → sum = -2-1+0+2 = -1 < 0 → left++
left=4, right=5 → sum = -2-1+1+2 = 0 ✓ → [-2,-1,1,2]

j=2, nums[j]=0:
left=3, right=5 → sum = -2+0+0+2 = 0 ✓ → [-2,0,0,2]

i=1, nums[i]=-1:
j=2, nums[j]=0:
left=3, right=5 → sum = -1+0+0+2 = 1 > 0 → right–
left=3, right=4 → sum = -1+0+0+1 = 0 ✓ → [-1,0,0,1]

结果: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]

去重与剪枝说明

技巧 位置 作用
去重 i/j 外层循环 避免同一元素重复使用
去重 left/right 找到解后 避免重复四元组
剪枝（最小和） 循环开头 提前终止不可能的情况
剪枝（最大和） 循环开头 跳过太小的情况

复杂度分析

指标 值
时间复杂度 O(n³) — 两层循环 + 双指针
空间复杂度 O(log n) — 排序递归栈（不计输出）

对比：两数之和 → 四数之和

问题 核心方法 时间复杂度
两数之和 哈希表 O(n)
三数之和 排序 + 双指针 O(n²)
四数之和 排序 + 两层循环 + 双指针 O(n³)

💡 通用套路：
“k” 数之和可以通过「固定
“k-2” 个数 + 双指针」将复杂度降到 O(n^(k-1))