刷题时最怕遇到什么？不是递归，不是动态规划，是那种看起来暴力就能解、但一提交就超时的大数组问题。三数之和与四数之和就是典型代表。暴力解法分别要到 O(n³) 和 O(n⁴)，数据量稍大就扛不住。但换个思路，用排序加双指针，复杂度直接掉到 O(n²) 和 O(n³)。这篇把核心逻辑拆清楚，看完能直接上手写代码。
先说三数之和。题目要求找出数组中所有和为零的不重复三元组。输入 [-1, 0, 1, 2, -1, -4]，输出应该是 [-1, -1, 2] 和 [-1, 0, 1] 这两组。暴力做法是三层循环枚举所有组合，O(n³) 的复杂度，n 超过 1000 就明显吃力。
优化从排序开始。数组排好序后，固定一个数，剩下就变成"找两个数凑出某个目标和"的经典问题。比如固定了 -1，就需要找两个数加起来等于 1。这时候双指针登场：一个放在固定位置的右边，一个放在数组末尾。和小了，左指针右移让总和变大；和大了，右指针左移让总和变小。找到匹配的就记录，然后两边都跳过重复值继续。
为什么排序后双指针有效？因为有序数组里，左移指针一定减小当前和，右移指针一定增大当前和。这个单调性保证了不会漏解，也避免了无意义的遍历。整个过程中，外层循环固定 n 个数，内层双指针最多走 n 步，总复杂度 O(n²)。去重也简单：固定元素时跳过重复的，找到解后两个指针各自跳过重复值即可。
四数之和的逻辑几乎一样，只是多固定一层。先排序，然后外层两个嵌套循环固定前两个数，剩下两个数用双指针找。比如数组 [1, 0, -1, 0, -2, 2] 目标和为 0，固定 -2 和 -1 后，就变成找两个数凑 3。双指针同样适用：左指针从第三个位置开始，右指针在末尾，根据和的大小调整位置。
复杂度对比很直观。四数之和暴力是 O(n⁴)，四层循环每个数都试。优化后两层循环加双指针，O(n³)。对于面试常见的 10⁴ 级别数据量，这意味着从几小时运算降到几秒可完成。
双指针的价值不止这两道题。它本质是利用有序结构的单调性，把"枚举所有可能"变成"有方向地收缩搜索空间"。两数之和、盛最多水的容器、滑动窗口最大值，底层都是这个思想。掌握之后，看到"有序数组""找满足条件的对/组"这类关键词，本能就会往双指针方向想。
最后提一个容易踩的坑：去重逻辑必须和指针移动配合好。三数之和里，找到一组解后，左右指针都要跳过所有相同值再移动，否则 [-1, 0, 0, 0, 1] 这种数据会输出多个 [ -1, 0, 1]。固定元素的循环也一样，当前数和前一个相同就直接 continue，避免重复固定。
这两道题的代码实现细节很多，但核心就三点：排序创造单调性、固定 k-2 个数把 k 数之和降为双指针问题、严格去重保证结果唯一。把这个框架吃透，五数之和、六数之和也能举一反三。
热门跟贴