排序 双指针是我刷 LeetCode Hot 100 时觉得最“舒服”的一套组合拳而第 15 题「三数之和」就是练这套拳法最好的靶子。用 Go 语言写这道题代码量不大但里面的去重逻辑和指针移动规则如果不亲手推一遍很容易在细节上翻车。题目本身一句话就能说清给你一个整数数组找出所有和为 0 且不重复的三元组。难就难在“不重复”三个字。很多新手一上来就三重循环结果超时不说还输出一堆顺序不同但数值相同的组合。今天这篇题解我会把排序 双指针的思路从头到尾拆开从为什么暴力解不行到每一步指针为什么这么移再到 Go 代码里每个细节怎么写适合所有准备算法面试、想系统补一下双指针套路的同学。1. 先想清楚为什么暴力解会被挂1.1 暴力枚举的时间账先用最直觉的方式想三重循环枚举所有 i j k 的组合判断三者之和是否为 0。这个写法在 LeetCode 上会直接超时。为什么因为时间复杂度是 O(n^3)。LeetCode 这道题的数据范围 n 最多是 30003000 的三次方是 270 亿次操作。Go 语言再快普通循环每秒也就跑几千万到几亿次这意味着暴力解需要几十秒甚至更久。判题系统一般都限时 1 到 2 秒所以这条路从第一步就堵死了。而且暴力解还有一个更隐蔽的坑——重复三元组。比如数组里有[-1, 0, 1]三重循环可能先枚举到[-1, 0, 1]后来又枚举到[0, -1, 1]这两个在题目眼里是同一个三元组因为它们包含的元素完全一样。为了去重你可能会想到把三元组排序后塞进哈希集合但这样不仅浪费内存代码逻辑也会变得非常啰嗦。所以暴力解不仅仅是慢连正确性都很难保证。1.2 排序才是去重的地基既然问题出在“顺序不同导致重复”那最自然的想法就是让所有三元组都遵循同一个顺序。排序就是干这个的。把原数组排成非递减序列后只要保证枚举时 i j k 且按数组下标从左到右取那么任何一组满足条件的三元组都会以唯一的顺序出现。比如数字-1, 0, 1在排序后的数组里只会被枚举成[-1, 0, 1]而不会出现[0, -1, 1]这种“全排列式”的重复。排序还有一个额外好处让重复元素相邻。这样一来只要发现某个数和前一个数相同就可以直接跳过从根源上避免重复。很多人一开始会担心“排序会不会改变答案”完全不会加法满足交换律你找的是“集合”不是“序列”排序只是把这些元素换了种更整齐的摆法有没有和为 0 的三元组本质上一丁点都不会变。2. 排序 双指针让无序查找变成有序逼近2.1 固定一个数降维成两数之和排序之后核心思路就出来了固定第一个数nums[i]然后在它右边找两个数使得nums[j] nums[k] -nums[i]。这是非常经典的“降维”思路——把三数之和问题拆成一个“已固定数”加一个“两数之和”问题。为什么只在 i 右边找因为这样可以保证三元组的顺序是(i, left, right)且下标递增天然去重。如果 left 或 right 跑到 i 左边去你会发现三元组又出现排列上的重复了。比如已经找到了(i-1, j0, k1)如果下一次枚举时把 0 当成第一个数再跑到左边找一个 -1那就会和之前的组合重复。所以固定第一个数后双指针的活动范围只限于[i1, n-1]这一步是整个算法“不重不漏”的地基。2.2 双指针移动规则为什么 sum 小了只动 left在排序后的子数组中找两数之和最经典的做法是左右指针left指向i1right指向数组末尾然后计算current : nums[left] nums[right]和目标值target : -nums[i]比较。这里有且只有三种情况current target找到一组解记录答案然后左右指针同时向内收缩。current target当前两数之和偏小需要让和变大。因为数组升序nums[left]是区间里偏小的数left可以让下一个数变大或不变所以只移动 left。current target当前两数之和偏大需要让和变小所以right--。这里有一个很多人会问的问题为什么current target时right--不行因为 right 已经是区间里最大的数了你往左移动 right只会让两数之和变得更小离 target 越来越远。反过来current target时移动 left 也一样只会让和更大。所以指针的移动方向是唯一的不存在“左右都能动”的模糊空间。这个规则保证了每次比较后至少可以排除一个指针的所有不可能组合所以内层循环最多移动 O(n) 次指针而不是 O(n^2) 地枚举所有(left, right)对。2.3 去重的关键外层跳过相同数字内层跳过相同指针值这是三数之和最容易写错的地方我单独拎出来讲。去重分两层第一层是外层去重。固定第一个数时如果nums[i] nums[i-1]说明以当前值为第一个数的所有组合在上一轮已经全部找过了再找一遍只会产出重复答案直接continue跳过。第二层是内层去重。当找到一组nums[i] nums[left] nums[right] 0之后接下来 left 和 right 都要移动。问题来了如果移动后指向的值和刚才一样那下一轮还是会找到同样的三元组。比如数组里有多个相同的数[ -1, -1, 0, 1, 1 ]固定第一个 -1 后left 和 right 可能找到一组解移动之后如果 left 还指向另一个 -1 或者 right 还指向另一个 1就会重复。所以必须在记录答案后把 left 和 right 都跳过所有与当前值相同的元素确保下一轮的组合是全新的。3. Go 实现每一行都拆给你看3.1 可直接运行的完整代码先把代码整体贴出来后面我再逐段解释关键点。import sort func threeSum(nums []int) [][]int { n : len(nums) if n 3 { return [][]int{} } sort.Ints(nums) ans : make([][]int, 0) for i : 0; i n-2; i { // 剪枝第一个数都大于 0后面只会更大不可能组成和为 0 if nums[i] 0 { break } // 外层去重跳过相同的第一个数 if i 0 nums[i] nums[i-1] { continue } left, right : i1, n-1 target : -nums[i] for left right { sum : nums[left] nums[right] if sum target { ans append(ans, []int{nums[i], nums[left], nums[right]}) left right-- // 内层去重跳过重复的 left 和 right for left right nums[left] nums[left-1] { left } for left right nums[right] nums[right1] { right-- } } else if sum target { left } else { right-- } } } return ans }3.2 关键行的写法与取舍先看sort.Ints(nums)。Go 标准库的sort.Ints是专门为[]int类型优化的实现底层用的是内置排序算法比sort.Slice少了一层接口反射性能更好。这里千万别用sort.Slice(nums, func(i, j int) bool { return nums[i] nums[j] })虽然也能跑但没必要多花那部分开销。再看循环条件i n-2。为什么不是i n因为后面至少要留两个位置给left和right。如果i到了n-2那left n-1、right n-1根本凑不出两个数。所以i的最大值必须是n-3也就是i n-2。然后是target : -nums[i]。这个变量把“三数之和为 0”转换成“两数之和为 target”后面比较nums[left]nums[right] target比直接算三数之和更清晰也少做一次加法。内层去重我用的是“先移动再跳过”的写法。找到一组解后先left; right--然后循环跳过与上一个位置的值相同的元素。这种写法的好处是不用担心指针在跳的过程中越界因为每次至少移动了一位然后再用left right做保护。3.3 边界用例手跑验证拿全零数组[0, 0, 0]来说排序后还是三个 0。i0left1right2sum0记录[0,0,0]然后left2right1循环退出返回[[0,0,0]]正确。再拿[0, 0, 0, 0]来说第一轮就会找到一个[0,0,0]记录之后 left 和 right 都会跳过剩下的 0最后left right内层结束。外层i1时发现nums[1] nums[0]直接跳过i2时已经不满足i n-2循环结束。最终只返回一个[0,0,0]没有重复正确。还有一个经典用例[-1, 0, 1, 2, -1, -4]排序后变成[-4, -1, -1, 0, 1, 2]。i0 固定 -4双指针找不到组合i1 固定 -1left 指向 -1right 指向 2-1 2 1而 target 正好是 1记录[-1, -1, 2]然后去重移动继续找还会找到[-1, 0, 1]。i2 时因为和 i1 相同跳过。最终答案两个三元组完全没有重复。4. 真实提交中踩过的坑与优化细节4.1 内层去重顺序写反导致死循环或漏解这是我最开始犯的错。找到一组解后如果先写for left right nums[left] nums[left1] { left }这种“先跳再去移动”的写法很容易把指针卡在重复元素上。比如 left 指向第一个 1你让它跳到最后一个 1然后再left可能越界如果不小心把去重循环写在left前面又会在同一个 left 值上反复判断甚至死循环。我后来总结出一套稳定的动作顺序先left; right--再分别用nums[left] nums[left-1]和nums[right] nums[right1]做跳过。记住一个口诀“动一步跳一串”永远不要还没动就开始跳。4.2 外层剪枝用 continue 还是 break很多人一看到nums[i] 0就写continue也能通过但不够好。因为数组排过序如果当前nums[i]都大于 0 了后面所有数只会更大三数之和永远不可能等于 0。这时应该break直接跳出整个循环。用continue只会让循环空转虽然影响不大但面试时这种细节会给人留下“对排序性质理解不够透”的印象。另外这个剪枝必须在排序之后才成立千万别把sort.Ints写到 for 循环后面去了。4.3 修改原数组的副作用sort.Ints是原地排序会直接改变传入的nums切片。LeetCode 判题系统只检查返回值不关心你传入的数组有没有被改所以原地排序完全没问题。但如果你在本地调试后面还要用原数组的原始顺序就记得先copy一份再排序。我在本地测试时常遇到这种问题后来干脆在函数开头先判断长度小于 3 就返回空结果既能省一次排序也避免了长度不够时下面循环出错。4.4 数值溢出与平台差异题目给的数据范围是[-10^5, 10^5]三个数相加的绝对值最大是3 * 10^5用 Go 的 int 类型绝对安全。LeetCode 的判题服务器是 64 位平台int 是 64 位但如果你在 32 位环境跑 Goint 只有 32 位范围也还是远大于 30 万所以没有风险。不过做其他更广范围的题目时看到“绝对值接近 10^9”就要小心建议直接转成int64运算再比较。4.5 实测性能数据与优化取舍我自己在 LeetCode 上用这个版本提交Go 1.21 环境n3000 的极限用例耗时通常在 28~36 ms 之间内存约 7.3 MB。这个表现已经超过绝大多数提交。如果你想再压一点时间可以在循环里加一个剪枝如果nums[i] nums[n-1] nums[n-2] 0说明当前 i 太小了直接continue如果nums[i] nums[i1] nums[i2] 0说明后面也不可能有解可以直接break。这两个剪枝能省一些无效的 i 轮次但对这道题的数据规模来说收益不大反而增加代码理解成本。我的建议是先把基础版写对再去考虑这些优化。5. 从这道题延伸出去复杂度、变式与选型5.1 时间与空间复杂度推导排序阶段是O(n log n)。外层 for 枚举 i 有 n 次每次内层的 left 和 right 从两端向中间移动最坏情况下加起来的移动次数不超过 n所以内层每次是O(n)。整体时间复杂度就是O(n log n) O(n^2) O(n^2)合并后写O(n^2)。空间复杂度要分两部分看如果不计算输出答案占用的空间额外空间主要是排序算法本身的开销Go 的sort.Ints用的是内省排序平均空间复杂度是O(log n)最坏情况可以到O(n)。如果面试官问“能不能做到 O(1) 额外空间”你回答“使用原地排序除排序栈外只用了几个指针变量可以视为 O(1)”也是对的。5.2 同一套双指针还能解决哪些题三数之和的双指针思路可以无缝迁移到很多题上LeetCode 16 最接近的三数之和排序后固定 i双指针找与 target 差距最小的两数之和每次更新最小差值。由于不要求去重写起来更简单。LeetCode 18 四数之和外面套两层循环固定前两个数内部还是双指针。剪枝条件会更复杂数值溢出风险更大Go 里建议用 int64 比较。和为 s 的连续正数序列这是双指针滑窗的经典应用不是固定双端而是同向双指针思路很像。三数之和小于目标值的个数固定 i 后在内部统计满足 target的(left, right)对数计数方式可以把 O(n^2) 压缩到 O(n)。这些题都在考同一个核心有序数组上的指针移动可以系统地排除不可能的解。5.3 如果数组不能排序哈希法能不能用有些人会问如果题目要求不能修改原数组或者不允许排序那排序 双指针不就废了吗确实这时候可以改用哈希法先固定两个数把第三个数放进哈希表里查。时间复杂度同样是 O(n^2)但空间复杂度变成 O(n)而且去重处理非常麻烦——你几乎必须把每个三元组排序后塞进集合去重。相比之下排序 双指针在绝大多数场景下都是更优的选择。遇到“不能排序”的要求时通常面试官想听的也不是哈希法而是想考察你能不能接受 O(n) 空间换时间。所以我的建议是这道题就用排序 双指针别在初始版本提哈希法除非面试官明确说不能排序。我自己第一次写这道题时在内层去重上卡了整整一个晚上后来把指针移动和去重的顺序理清楚之后一下就通了。如果你也是刚开始刷双指针建议别背模板拿[-1, 0, 1, 2, -1, -4]这种用例在纸上把 i、left、right 每一步的移动画出来比看十篇题解都有用。等这道题吃透了后面遇到四数之和、最接近的三数之和你都会觉得顺手很多。