企业官网建设流程全解析

四数之和这道题，刷LeetCode的人基本都绕不过去。它看起来只是在三数之和后面加了一个数，但真到自己动手写的时候，很多人会发现完全不是那么回事——去重逻辑绕晕、int溢出踩坑、剪枝不到位导致超时，各种问题接踵而至。我最早写这道题时，直接用四层循环暴力解，结果是正确性没问题，一旦数据量上来就当场TLE。后来老老实实把双指针的思路吃透，才明白这道题真正想考察的不是“你会不会套模板”，而是你对排序、指针收缩、去重边界和剪枝优化的综合理解。

这篇文章我会把四数之和从思路到实现完整讲一遍，重点放在为什么要这么做、双指针为什么能降复杂度、去重和剪枝的具体细节，以及我在调试过程中踩过的坑。无论你是刚开始刷双指针题目的新手，还是已经写过但总在边界条件上栽跟头的进阶选手，这篇文章都值得你花十分钟读透。

1. 从暴力枚举到双指针收缩：四数之和的思路是怎么长出来的

1.1 暴力解法的天花板在哪里

题目描述很简单：给你一个由整数组成的数组 nums，和一个目标值 target，找出所有不重复的四元组[nums[a], nums[b], nums[c], nums[d]]，满足四个数之和等于 target，并且每个四元组内部按升序排列。

最直白的思路就是四层循环：枚举 a、b、c、d 四个下标，检查nums[a] + nums[b] + nums[c] + nums[d] == target，满足就把结果存下来。四层循环的时间复杂度是 O(n⁴)，在力扣的测试数据下，n 稍微过百就非常吃力，更别说去重逻辑还要用集合或者排序来额外处理。

暴力解法其实还有一个很隐蔽的问题：去重成本高。即使你用Set去重，存储和哈希的开销也会拖慢整个程序。所以这道题如果以暴力方式写，大概率会超时，这也是它被归为重点题目的原因——它逼着你寻找更优的解法。

1.2 双指针为什么能把复杂度降一维

双指针的核心思想，本质上来自“有序数组”带来的性质。一个有序数组里，如果你把两个指针分别放在区间两端，通过比较当前和与目标值的大小，可以确定性地知道下一步该移动左指针还是右指针，从而在 O(n) 时间内完成两数之和的查找。这个过程不需要额外哈希表，也不需要回溯。

放到四数之和这道题里，思路就变得清楚了：先排序，然后用两层循环固定前两个数，剩下两个数用双指针在区间内寻找。这样四层循环就降成了两层循环加一层线性扫描，整体复杂度从 O(n⁴) 降到了 O(n³)。排序本身是 O(n log n)，相比 O(n³) 可以忽略不计。

我打个比方帮助理解：假设你在一列升序排列的数字里找两个数凑成一个固定值，最笨的办法是把所有组合都试一遍；但如果利用“当前和太小就说明左边的数不够大，把左指针右移；当前和太大就说明右边的数太大，把右指针左移”这个规律，每一步你都能排除掉一大片不可能的组合，这就是双指针省时间的本质。

2. 排序、双层固定、双指针收缩：核心实现逐行拆解

2.1 排序是双指针能成立的前提

很多人写这道题时，第一步就忽略了排序的重要性，直接开始枚举。不排序，双指针根本无法工作，因为只有数组有序，你才能根据和的大小判断该移动哪个指针。所以代码的第一步一定是：

nums.sort()

这一步做完，后面所有逻辑的地基才算打好了。Python 里 sorted 会返回新列表，nums.sort()是原地排序，省内存，建议直接原地排序。

排序还有一个附加好处：它让“去重”变得非常简单。相同的数在排序后会挤到一起，你只需要在循环时跳过和前一个位置相同的元素，就能保证同一个值的下标不会重复枚举。这一点后面会详细展开。

2.2 外层两重循环：固定住前两个数

排序之后，我们用两个变量 i 和 j 分别代表第一个数和第二个数的下标。i 从 0 遍历到 n-4（因为后面至少要留三个位置给 j、left、right），j 从 i+1 遍历到 n-3。这一步就是“固定两个数，把四数之和转化为两数之和”的核心。

外层两个循环里，需要做两件事：一是跳过重复值，二是做初步剪枝。跳过重复的逻辑是：

if i > 0 and nums[i] == nums[i-1]: continue

为什么是nums[i] == nums[i-1]而不是nums[i] == nums[i+1]？因为前者表示“当前这个值已经作为第一个数处理过了”，后者在 i 还没往后走时就把当前的重复值跳过了，会导致你漏掉正确结果。同理，j 的循环也要跳过重复值：

if j > i + 1 and nums[j] == nums[j-1]: continue

这里尤其要注意 j 的去重起点是i + 1，因为 j 的第一个位置无论和前一个数相不相等都要处理，不能一上来就跳过。

2.3 内层双指针：移动规则与命中处理

固定好 i 和 j 之后，剩下两个数的查找就是经典的双指针逻辑。设 left = j + 1，right = n - 1，然后计算当前四数之和 total：

total = nums[i] + nums[j] + nums[left] + nums[right]

比较 total 和 target：

• 如果 total 等于 target，说明找到了一组答案。此时记录结果，然后移动 left 和 right 跳过所有重复值，最后再各自向中间收缩一步。
• 如果 total 小于 target，说明四数之和太小，需要更大的数，让 left 右移。
• 如果 total 大于 target，说明四数之和太大，需要更小的数，让 right 左移。

为什么要同时跳过重复值？因为如果不跳，left 移动到下一个相同数值时，和 right 的组合依然等于 target，你会把完全相同的四元组重复加入结果，这就是去重的第三处关键点。

命中 target 后，两个指针必须同时收缩。这一点很多初学者想不通：为什么左指针右移之后，右指针不能保持不变呢？因为当前的总和已经等于 target，如果只移动一边，新的和一定不等于 target（数组有序且已跳过重复值），所以两边都必须动，才能进入新的搜索区间。

完整的核心代码段如下：

def fourSum(nums, target): nums.sort() n = len(nums) res = [] for i in range(n - 3): if i > 0 and nums[i] == nums[i-1]: continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j-1]: continue left, right = j + 1, n - 1 while left < right: total = nums[i] + nums[j] + nums[left] + nums[right] if total == target: res.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 res

这段代码已经能 AC 大部分测试数据了。但如果你想在数据量很大的情况下依然保持不错的性能，就得看下面这节剪枝优化。

3. 去重与剪枝：从超时到AC的分水岭

3.1 三处关键去重，一处都不能省

四数之和的去重，一共有三处位置，缺一不可。

第一处是 i 层面的去重。如果不加，数组[2, 2, 2, 2, 2]这种用例会输出大量重复四元组。第二处是 j 层面的去重，起点必须是i + 1，理由前面已经说过。第三处是 left 和 right 层面的去重，也就是命中 target 之后，连续跳过重复值。

第三处有一个容易被忽略的细节：跳完重复后，还需要最后执行left += 1和right -= 1。很多人写完两个 while 循环后就直接进入下一轮 while，结果 left 还是指向最后一个重复元素，right 也还是指向最后一个重复元素，下一轮比较时又得到一个等于 target 的和，导致死循环。

我在实际调试中见过太多这样的死循环了，建议你在写的时候，把“跳过重复”和“指针收缩”这两步分开写清楚，不要合并成一个步骤，可读性和正确性都能提升。

3.2 两个方向的剪枝优化

剪枝是四数之和里最能体现水平的部分。排序之后数组有序，我们可以利用“当前情况下能得到的最小和、最大和”来做提前终止判断，减少不必要的循环。

第一个剪枝：如果当前固定的 nums[i] 加上其后最小的三个数（nums[i+1]、nums[i+2]、nums[i+3]）已经大于 target，那说明 i 再往后取只会更大，直接 break 整个外层循环。因为数组升序，i 越往后，nums[i] 越大大，最小的四个数之和只会越来越大，后面的情况不可能满足条件。

第二个剪枝：如果 nums[i] 加上数组最后三个最大的数（nums[n-1]、nums[n-2]、nums[n-3]）仍然小于 target，说明 i 这个位置作为第一个数太小了，就算加上最大的三个数都不够，于是直接 continue，跳到下一个 i。

同样的剪枝逻辑，在内层 j 的循环里也要写一遍。把 j 的剪枝代码补上，整体效率能提升 20% 到 30%：

for i in range(n - 3): if i > 0 and nums[i] == nums[i-1]: continue # 第一层剪枝：当前最小的四数之和大于 target，直接跳出 if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target: break # 第二层剪枝：当前最大的四数之和小于 target，i 换下一个 if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target: continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j-1]: continue # 内层剪枝 if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target: break if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target: continue ...

要注意：target 为负数时，这两个剪枝依然成立，因为排序后的数组依然满足“最小四数之和递增”的性质，剪枝逻辑不依赖 target 的正负。

4. 溢出、空数组、临界值：调试四数之和的实战记录

4.1 int溢出的经典翻车现场

如果你用的是 C++ 或 Java，四数之和有一个特别经典的坑：整数溢出。力扣的测试数据里有一个用例是nums = [1000000000, 1000000000, 1000000000, 1000000000]，target 也是很大的数。四个 10 亿相加等于 40 亿，已经超过了 int 类型的上限 2147483647，于是计算结果会变成负数，导致比较逻辑完全混乱。

解法有两个思路：

• 把四个数逐个强制转换为 long long 再相加，避免中间过程溢出；
• 在循环内部用 long long 变量承接四个数的和，再与 target 比较。

第一次遇到这个问题时，我花了大半天时间才定位到是溢出，因为逻辑查了很多遍都没错，最后打印中间量才发现问题。这里提醒你：只要目标值和你数组中的数可能接近 int 上限，任何涉及四数相加的地方都要先把类型放大。Python 没有这个问题，因为它的整数是任意精度的，但 C++ 和 Java 一定要小心。

4.2 边界条件与测试用例设计

除了溢出，还有几个边界条件在实际写代码时很容易漏掉：

• 数组长度小于 4，直接返回空数组；
• 数组元素全为负数时，target 也可能是负数，不能默认 target 为正；
• 数组中大量重复元素时，去重逻辑是否真的生效；
• left 和 right 在移动过程中，会不会出现下标越界。

我的习惯是写完代码后，先用几组经典用例做回归测试。最基本的用例包括：nums = [1, 0, -1, 0, -2, 2], target = 0，期望输出[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]；再跑一个全相同的数组；再跑一个数组长度刚好为 4 的用例；最后跑一个目标值非常极端的用例。这套组合拳打下来，基本能覆盖绝大多数边界问题。

调试的时候我还建议你在关键循环里打印i, j, left, right, total这几个值。很多人觉得打印日志很麻烦，但遇到死循环或者结果缺失时，这一步往往能一分钟定位问题。尤其是去重逻辑报错的场景，打印出当前比较的下标，你一眼就能看出是不是漏了“跳过重复值”那一步。

5. 从四数之和到K数之和：双指针思路的举一反三

5.1 KSum问题的通用框架

四数之和掌握了之后，你会发现三数之和、五数之和、K数之和本质上都是一个套路。把 KSum 写成一个递归函数，固定一个数，然后在剩余数组中找 K-1 数之和；当 K 等于 2 时，使用双指针在线性时间内查找。这个框架可以适配任意 K 值，面试时能说出来，是很大的加分项。

递归框架的伪代码大概是这样的：

def kSum(nums, target, k, start): res = [] if k == 2: left, right = start, len(nums) - 1 while left < right: if nums[left] + nums[right] == target: res.append([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 nums[left] + nums[right] < target: left += 1 else: right -= 1 return res for i in range(start, len(nums) - k + 1): if i > start and nums[i] == nums[i-1]: continue for sub in kSum(nums, target - nums[i], k - 1, i + 1): res.append([nums[i]] + sub) return res

递归版本的时间复杂度是 O(n^(k-1))，优势是代码简短统一，适合 K 不固定的场景；缺点是递归调用有一定开销，K 很小的时候不如直接写嵌套循环清晰。四数之和这种 K = 4 的题目，面试官更想看的是你能不能高效地写出两层循环加双指针，递归方案可以作为扩展话题提一嘴。

5.2 双指针题型的适用边界

双指针并不是万能的，它最大的前提是“数组有序”或者“问题能通过有序性来排除搜索范围”。常见适用场景有这么几类：

• 两数之和（有序数组版）；
• 三数之和、四数之和；
• 盛最多水的容器；
• 接雨水；
• 删除有序数组中的重复项。

这些题目的共同特征是：都利用了对撞指针在有序区间内快速收缩，达到 O(n) 或 O(n²) 级别的复杂度。遇到无序数组时，要么先排序，要么考虑哈希表方案，两者各有优劣。排序会改变元素顺序，如果题目要求返回下标且答案依赖原始下标，就不能直接排序，要另想思路。

我从自己的刷题经验来看，四数之和真正难住人的不是思路本身，而是去重和边界。很多人知道双指针这个方法，但写出来总差一点。建议你动手之前先在纸上把 i、j、left、right 四个指针的可能位置画一遍，把三个去重位置标注出来，再动笔写代码，一次写对的概率会高很多。如果一次没过，也别急着看题解，把报错的用例打印出来，对照上面的检查清单，往往能自己找出问题。