算法打卡第十四天/四数之和

第14天 四数之和（LeetCode 18）

一、今日学习任务

第14天 双指针 + 数组去重

1. 四数之和
题目建议：本题为三数之和的延伸题型，整体解题框架一致，核心采用排序+双指针实现降维优化。重点对比本题与 454.四数相加II 的本质区别，理解两题难度差异的核心原因。代码细节繁杂，多层级去重、边界判断、防止溢出都是高频易错点，需要耐心梳理细节，熟练掌握多数之和通用解题套路。
题目链接：https://leetcode.cn/problems/4sum/
视频讲解：https://www.bilibili.com/video/BV1DS4y147US

二、初次解题思路和思考

拿到题目第一想法是暴力四层循环，枚举数组中所有四元组，判断四数之和是否等于目标值 target。
暴力解法缺陷十分明显：

1. 时间复杂度极高，四层循环时间复杂度为 O(n^4)，数据量稍大直接超时，完全无法通过题目限制。

2. 会产生大量重复四元组，后续去重成本极高，代码冗余且效率低下。

3. 没有利用数组有序、双指针压缩区间的优化思想，解题思维僵化。

联想到之前三数之和的做法，同时对比上一题 454.四数相加II：

• 四数相加II：四个独立数组、无需去重、只统计组合数量，适合哈希表分组计数；

• 本题四数之和：同一个数组内选取四元素、不能重复四元组、需要返回具体集合，无法用哈希简单处理，只能依靠排序加双指针。

核心优化思路：
先对数组整体排序，固定两层循环枚举前两个数，再用左右双指针分别指向第三、第四个数，通过移动指针动态调整四数总和，逼近 target。
通过排序配合多层级去重，既降低时间复杂度，又自动规避重复结果，是本题最优解法。

三、写代码时核心注意点

1. 双层循环固定前两个数，双指针控制后两个数
第一层遍历 i ，第二层遍历 j = i+1，左指针 left = j+1，右指针 right = 数组末尾。

2. 多层严谨去重（本题最大难点）

• i 层级去重：当前i与上一轮i元素相同时，直接跳过，避免重复组合；

• j 层级去重：j 在 i 范围内，相同元素跳过；

• 双指针去重：找到合法答案后，收缩左右指针并跳过相同元素，防止重复集合。

3. 指针移动规则

• 四数和 > target：右指针左移，减小总和；

• 四数和 < target：左指针右移，增大总和；

• 等于 target：记录答案，同时收缩左右指针并去重。

4. 数据溢出问题
数组元素可正可负、数值范围大，四数累加容易溢出，计算时注意合理书写表达式，防止int溢出报错。

5. 边界限制
严格保证指针大小关系：i < j < left < right，保证元素选取不重复、不交叉。

四、操作

测试示例

输入：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. 明确区分 四数之和 与 四数相加II 的核心差异：同数组去重解集问题用排序+双指针，多数组计数问题用哈希分组，不再混淆两类题型。

2. 熟练掌握 n 数之和通用模板：排序 + 固定前 n-2 层循环 + 双指针收缩，形成标准化解题思维。

3. 深刻理解多层级去重逻辑，明白有序数组下跳过重复元素的关键作用，解决重复解集的核心痛点。

4. 注意整型溢出细节，学会用long long接收累加和，养成代码边界与数据范围的严谨习惯。

5. 进一步巩固双指针算法思想，学会通过区间收缩动态调整数值大小，高效缩小搜索范围，大幅降低时间复杂度。