拓冰网站定制 
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]]解题思路排序 双指针核心思想四数之和 → 固定两个数 两数之和双指针排序数组两层循环固定前两个数“i” 和“j”用双指针“left” 和“right” 在剩余区间找两数之和去重跳过重复的枚举值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]i0, nums[i]-2:j1, nums[j]-1:双指针 left2, right5 → sum -2-102 -1 0 → leftleft3, right5 → sum -2-102 -1 0 → leftleft4, right5 → sum -2-112 0 ✓ → [-2,-1,1,2]j2, nums[j]0:left3, right5 → sum -2002 0 ✓ → [-2,0,0,2]i1, nums[i]-1:j2, nums[j]0:left3, right5 → sum -1002 1 0 → right–left3, right4 → sum -1001 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)) 元宝 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]]解题思路排序 双指针核心思想四数之和 → 固定两个数 两数之和双指针排序数组两层循环固定前两个数“i” 和“j”用双指针“left” 和“right” 在剩余区间找两数之和去重跳过重复的枚举值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]i0, nums[i]-2:j1, nums[j]-1:双指针 left2, right5 → sum -2-102 -1 0 → leftleft3, right5 → sum -2-102 -1 0 → leftleft4, right5 → sum -2-112 0 ✓ → [-2,-1,1,2]j2, nums[j]0:left3, right5 → sum -2002 0 ✓ → [-2,0,0,2]i1, nums[i]-1:j2, nums[j]0:left3, right5 → sum -1002 1 0 → right–left3, right4 → sum -1001 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))