LeetCode 每日一题 #18：四数之和｜Python 排序 + 双重循环 + 双指针
几年前我准备求职时，也曾一头扎进 LeetCode 的题海。从最初的“看题懵圈”到后来能在面试中从容写出最优解，每天坚持刷一道题成了我提升算法能力最有效的方式。那段经历不仅帮我顺利拿到心仪 offer，更让我养成了系统思考和高效编码的习惯。
如今工作稳定了，终于有时间把当年的刷题笔记重新整理、优化，并用 Python 语言 逐题讲解清楚。希望能帮助正在准备面试、转行或想夯实基础的你——少走弯路，高效进步。
关键词：双指针、排序、四数之和、去重、剪枝优化
难度：中等
推荐指数：⭐⭐⭐⭐☆（高频变种题，考察代码鲁棒性）
题目描述
给你一个由 n 个整数组成的数组 nums 和一个目标值 target。
请你找出所有不重复的四元组 [a, b, c, d]，使得 a + b + c + d == target。
答案中不能包含重复的四元组。
示例
输入: nums =[1,0,-1,0,-2,2], target =0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 输入: nums =[2,2,2,2,2], target =8 输出:[[2,2,2,2]]约束条件
1 <= nums.length <= 200-10⁹ <= nums[i] <= 10⁹-10⁹ <= target <= 10⁹
解题思路
本题是 第 15 题《三数之和》的直接推广。核心思想不变：
排序 + 固定前两个数 + 双指针处理后两个数
但由于维度增加，去重和剪枝逻辑更复杂，需格外小心。
整体框架：
- 排序数组 → 支持双指针与去重
- 外层两重循环：
i：第一个数（范围[0, n-4]）j：第二个数（范围[i+1, n-3]）
- 内层双指针：
left = j+1,right = n-1- 寻找
nums[left] + nums[right] == target - nums[i] - nums[j]
- 关键挑战：
- 去重：
i、j、left、right四处均需跳过重复值 - 剪枝：提前终止不可能的分支，避免超时
- 去重：
Python 代码实现
解法：排序 + 双重循环 + 双指针（标准解法）
classSolution:deffourSum(self, nums: List[int], target:int)-> List[List[int]]: nums.sort() n =len(nums) result =[]for i inrange(n -3):# 去重 iif i >0and nums[i]== nums[i -1]:continue# 剪枝1：最小四数和 > target → 后续无解if nums[i]+ nums[i +1]+ nums[i +2]+ nums[i +3]> target:break# 剪枝2：最大四数和 < target → 当前 i 无解if nums[i]+ nums[n -3]+ nums[n -2]+ nums[n -1]< target:continuefor j inrange(i +1, n -2):# 去重 jif j > i +1and nums[j]== nums[j -1]:continue# 剪枝3：当前最小四数和 > targetif nums[i]+ nums[j]+ nums[j +1]+ nums[j +2]> target:break# 剪枝4：当前最大四数和 < targetif nums[i]+ nums[j]+ nums[n -2]+ nums[n -1]< target:continue left, right = j +1, n -1while left < right: s = nums[i]+ nums[j]+ nums[left]+ nums[right]if s == target: result.append([nums[i], nums[j], nums[left], nums[right]])# 去重 left 和 rightwhile left < right and nums[left]== nums[left +1]: left +=1while left < right and nums[right]== nums[right -1]: right -=1 left +=1 right -=1elif s < target: left +=1else: right -=1return result 🔍 关键逻辑详解
去重策略
i去重：if i > 0 and nums[i] == nums[i-1]: continue
→ 跳过与前一个相同的起始值j去重：if j > i+1 and nums[j] == nums[j-1]: continue
→ 注意条件是j > i+1，而非j > 0，确保只跳过本轮内的重复
为什么j的判断是j > i + 1？
因为j从i+1开始，第一次出现nums[j]是合法的，只有当j至少是i+2且与前一个相同时才跳过。
四大剪枝优化
- 外层最小和剪枝：若
i开头的最小四数和已超target，直接break（后续更大） - 外层最大和剪枝：若
i开头的最大四数和仍不足，continue（换更大的i） - 内层最小和剪枝：固定
i,j后，若最小和超target，break内层 - 内层最大和剪枝：固定
i,j后，若最大和不足，continue（换更大的j）
注意：由于target可能为负数，不能省略任何剪枝条件！
例如：nums = [-5, -4, -3, -2, -1], target = -10，若错误地认为“和为负就跳过”，会漏解。
双指针内层去重
- 找到一组解后，跳过所有相同的
left和right，再各移动一步 - 与三数之和完全一致
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(n³) |
| 空间复杂度 | O(1)（不计输出） |
排序 O(n log n)，两重循环 O(n²)，双指针 O(n) → 总体 O(n³)
小结 & 面试技巧
- 与三数之和的关系：
- 相同：排序 + 双指针 + 去重
- 不同：多一层循环，剪枝条件更复杂
- 三大易错点：
j去重条件写错（应为j > i + 1）- 忽略
target为负数，导致剪枝逻辑错误 - 剪枝时未检查索引越界（但本题因循环范围已保证安全）
- 扩展思考：
- 如何实现通用的
kSum函数？（递归 + 双指针） - 若允许重复四元组，如何修改？（删除所有去重逻辑）
- 如何实现通用的
面试话术：
“我在三数之和的基础上，增加了一层外循环固定第二个数。为提升效率，我加入了四重剪枝：在外层和内层分别判断最小/最大可能和是否超出目标。去重时，我确保只跳过本轮内的重复值。”
下期预告
明天我们将挑战第 19 题：删除链表的倒数第 N 个结点，带你用双指针一次遍历搞定链表定位！
坚持每天一道 LeetCode，用 Python 写出优雅代码，夯实算法基础，拿下心仪 Offer！
关注专栏，不错过每日更新！
