这道题我刷了好几遍每次在面试前都会把它翻出来重新写一遍。不是说它难而是它在 LeetCode Hot 100 里的地位很特别——你几乎不可能在真正的面试里碰到一模一样的三数之和但面试官完全可能换一个壳考你排序加双指针这个组合套路。用 Go 语言实现三数之和既能验证你对切片的操作是否熟练也能检验你对去重逻辑的理解是否透彻。这篇文章就把这道题的完整解法、推导过程、Go 实现细节和我在提交过程中踩过的坑一次性讲清楚。先说结论排序加双指针是这道题的标准解法时间复杂度 O(N^2)空间复杂度 O(log N) 到 O(N)取决于排序实现。只要你把去重逻辑写对一次性通过所有测试用例没有任何问题。1. 这道题为什么值得出现在 Hot 100先看暴力解法的死穴1.1 题目到底在问什么隐藏的去重要求题目描述很简单给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 a、b、c使得 a b c 0。请你找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。这里有一个容易被新手忽略的重点不重复这三个字。比如数组是 [-1, 0, 1, 1]你找到 [-1, 0, 1] 之后后面再用第二个 1 组合出的 [-1, 0, 1] 就算重复不能输出。LeetCode 的判题系统会先对结果做排序和去重再比较但你的代码如果输出两个同样的三元组直接判错。所以这道题表面上是一道求和题实际上是一道枚举加去重的组合问题。这个隐藏要求决定了我们后续所有设计的方向。还有一个细节返回的是三元组的列表每个三元组内部的数字可以按任意顺序返回但最终提交时系统会统一排序比较。所以你在代码里返回 [0, -1, 1] 和 [-1, 0, 1] 都行只要数值集合相同就算通过。1.2 暴力三重循环为什么不行去重比枚举更麻烦最直接的思路就是三重循环枚举所有 i、j、k检查 nums[i] nums[j] nums[k] 是否等于 0。代码写起来很简单func threeSumBrute(nums []int) [][]int { n : len(nums) res : [][]int{} for i : 0; i n; i { for j : i 1; j n; j { for k : j 1; k n; k { if nums[i] nums[j] nums[k] 0 { res append(res, []int{nums[i], nums[j], nums[k]}) } } } } return res }这段代码能跑通样例但存在两个致命问题。时间复杂度是 O(N^3)。当数组长度 N 3000 时内层循环要执行约 45 亿次LeetCode 上直接超时。Hot 100 里的题通常 N 的上限是 3 * 10^4 甚至更大暴力解法在实际数据规模下没有任何存活空间。第二个问题更隐蔽三重循环天然会产生大量重复三元组。比如数组是 [-1, 0, 1, 2, -1, -4]你去重最简单的方式是把每个三元组排序后作为 key 存进 map。但这里有个陷阱Go 的切片不能直接作为 map 的 key你只能转成字符串或者用组合后的整数键。把三元组排序再拼成字符串这个操作本身就有 O(3 log 3) 的开销而且 map 的存储会拖垮内存。所以说暴力解法不是不够优雅的问题而是根本不可行。我们需要一个既能降低复杂度、又能天然避免重复的方案。这就引出了排序加双指针。2. 排序 双指针把 O(N^3) 拉回 O(N^2) 的完整推演2.1 排序带来什么让数组有了方向先看一个朴素的直觉如果数组是乱序的你可以从任何位置开始找三个数方向完全不可控。但如果你先把数组排序比如从小到大排好那么当你固定第一个数 a 时剩下两个数 b 和 c 的搜索空间变成了一个有序区间。在有序数组里找两个数和等于 target这个问题可以用双指针从两端往中间夹逼而夹逼的过程保证每一种组合只会被检查一次。这就是排序带来的第一个好处双指针可以工作。第二个好处是排序后相同的元素会相邻排列这让去重变得极其简单——跳过相邻的重复元素即可。为什么双指针在有序数组里能高效找到两数之和因为当你把 left 指针放在区间最左端最小值right 指针放在区间最右端最大值它们的和是当前区间内最小加最大的结果。如果这个结果比 target 大说明右边的最大值太大需要把 right 向左移动一位如果比 target 小说明左边的最小值太小需要把 left 向右移动一位。每次比较后至少排除一个元素所以整体只需要线性时间。用一个生活化的类比你在一个从小到大的队伍里找两个人让他们身高之和等于某个固定值。最矮的和最高的站在一起如果两人身高加起来太高就让最高的往前走一位如果太低就让最矮的往后走一位。这样每走一步就排除一个人不会漏掉任何可能。2.2 双指针如何工作固定一个夹逼另外两个三数之和的完整策略是首先对 nums 排序。用 for 循环固定第一个数 nums[i]。在 i1 到 n-1 的区间内用 left 和 right 两个指针找两个数使 nums[left] nums[right] -nums[i]。找到一组就记录然后移动指针继续找。为什么要固定第一个数而不是固定中间那个或者让三个指针一起动因为固定一个是最自然的降维思路三数之和变成了单指针遍历一个数 双指针找两数之和整体复杂度是 O(N * N)。固定哪个数其实都可以但固定第一个数时搜索区间始终在它的右侧能避免把同一个三元组重复枚举。这里需要特别注意一个细节当 i 固定后left 必须从 i1 开始而不是从 0 开始。如果你让 left 从 0 开始那么当 i1 时你可能会在 left 指向 nums[0] 的情况下组合出 (nums[1], nums[0], nums[k])这和 i0 时组合出的 (nums[0], nums[1], nums[k]) 本质上是同一个三元组。为了彻底避免这种重复所有搜索都在当前位置的右侧进行是最干净的约定。有人会问为什么不用哈希表法遍历 i 和 j然后在 map 里找第三个数这个思路对应的是两数之和的扩展版时间复杂度也是 O(N^2)但问题在于去重非常麻烦。你需要在结果集合里手动去掉重复的三元组而且 map 对负数和大数的处理会引入额外的哈希计算成本。排序加双指针之所以成为这道题的标准解正是因为它在 O(N^2) 的时间里同时解决了去重问题。2.3 一个简单例子手推全过程用一个具体的数组走一遍nums [-1, 0, 1, 2, -1, -4]。第一步排序后得到 [-4, -1, -1, 0, 1, 2]。i 0nums[i] -4目标 target 4。left 1right 5。nums[1] nums[5] -1 2 1 4left。nums[2] nums[5] -1 2 1 4left。nums[3] nums[5] 0 2 2 4left。nums[4] nums[5] 1 2 3 4left。left right结束。这一轮没有找到。i 1nums[i] -1目标 target 1。left 2right 5。nums[2] nums[5] -1 2 1 target记录三元组 [-1, -1, 2]。去重左边 nums[2] nums[3]都是 -1left 跳到 3右边没有相同。然后 leftright--left 4right 4结束。i 2nums[i] -1。注意此时 nums[2] nums[1] -1直接跳过否则会找到重复的 [-1, -1, 2]。i 3nums[i] 0目标 target 0。left 4right 5。nums[4] nums[5] 1 2 3 0right--。left right结束。i 4nums[i] 1目标 target -1。left 5right 5不满足 left right结束。同时 nums[i] 0可以提前 break。最终结果只有 [[-1, -1, 2]]。注意数组里其实还有 [-1, 0, 1] 这个组合但去重后只算一种。上面的过程里 i1 之后其实 nums[i] -1 和前面的重复被跳过了所以 [-1, 0, 1] 在 i1 时已经考虑过nums[1] -1, nums[3] 0, nums[4] 1只是我在上面的推演中因为 left 指针先去重跳到了 4漏写了中间过程。你实际跑代码时会发现i1 这一轮确实能同时检查到 [-1, -1, 2] 和 [-1, 0, 1]。3. Go 语言实现完整代码与每个关键行的取舍3.1 可运行的 Go 解法直接给出可以提交到 LeetCode 的完整代码import sort func threeSum(nums []int) [][]int { n : len(nums) if n 3 { return [][]int{} } sort.Ints(nums) res : 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 { res append(res, []int{nums[i], nums[left], nums[right]}) // 跳过重复的第二个数 for left right nums[left] nums[left1] { left } // 跳过重复的第三个数 for left right nums[right] nums[right-1] { right-- } // 找到一组后两个指针同时向内收缩 left right-- } else if sum target { left } else { right-- } } } return res }这段代码在 LeetCode 官方题解里就是标准示例Go 语言版本可以直接通过。3.2 为什么第一步是 sort.IntsGo 的 sort 包提供了内置的整数切片排序函数 sort.Ints底层是 pdqsort一种结合了插入排序、堆排序和快速排序的混合算法平均时间复杂度 O(N log N)实际运行速度很快。代码里第一件事就是判空if n 3 直接返回空二维切片。这一步不是可选的因为三数之和要求至少三个元素如果切片长度小于 3后面的循环条件 i n-2 本身就不会进入但显式判空能提高代码可读性也能避免一些粗心大意导致的数组越界问题。排序为什么必须放在前面因为整个双指针算法依赖有序性。如果不排序右指针从最右端往左移动时不能确定当前 right 指向的是不是当前区间内最大的数那么移动指针的规则就完全失效整个 O(N) 的两数搜索无法成立。3.3 去重的三处细节少一处就 WA这是这道题最容易出错的地方全网的提交记录里大量 WA 都出在去重逻辑上。完整答案需要三处去重第一处外层循环跳过重复的 i。当 i 0 且 nums[i] nums[i-1] 时直接 continue。理由很直观既然上一次已经用 nums[i-1] 作为第一个数搜索过所有组合现在再用相同的数搜一遍得到的三元组一定前面都有了。这里有个常见的迷惑点为什么是 nums[i] nums[i-1] 而不是 nums[i] nums[i1]如果我写成后者那么在遇到连续三个相同数字时可能会跳过有用的组合。比如 nums [-1, -1, -1, 2, -1]用 nums[i] nums[i1] 判断第一个 -1 会被跳过但第一个 -1 加上后面两个数可能构成唯一有效解。更关键的是比较 nums[i] 和它左边已经处理过的元素意味着这个值我已经处理过了不再处理逻辑上是干净的。比较右边则意味着这个值我还没处理就不要了这是错误的。第二处内层循环找到一组答案后跳过重复的 nums[left]。为什么要在找到答案后去重而不是在移动 left 之前因为如果 left 和 left1 的值相同你在当前 left 位置找到的答案如果记录那么下一个 left 位置找到的很可能是同一个三元组必须跳过。去重的标准写法是 for left right nums[left] nums[left1] { left }。第三处同样地找到答案后跳过重复的 nums[right]。对称处理for left right nums[right] nums[right-1] { right-- }。这三处缺一不可。只去重 i 而不去重 left/right当数组里重复元素较多时会产生大量重复三元组只去重 left/right 而不去重 i外层循环会重复枚举一模一样的组合。3.4 边界条件的处理顺序代码里两个剪枝条件的顺序值得注意if nums[i] 0 { break } if i 0 nums[i] nums[i-1] { continue }为什么先判断大于 0 再判断重复因为数组已经从小到大排序一旦 nums[i] 0无论后面怎么选三个数的和都不可能等于 0正数加正数加正数永远是正数直接 break 终止整个循环这是最有效的剪枝。而重复判断只是跳过当前 i循环还会继续所以先做能提前终止的判断更合理。如果你把顺序反过来在 nums[i] 0 时仍然去做重复判断虽然结果一样但逻辑上不干净而且多了一次无意义的比较。另外一个细节是循环条件的写法for i : 0; i n-2; i这里 i 最大到 n-3保证后面至少还有 left 和 right 两个位置可以取。有人喜欢写成 i n内层再判断 left right这样也能跑但循环会多执行两次空操作没必要。4. 最容易翻车的排查链路我在提交时踩过的坑4.1 坑一找到答案后忘了移动指针直接超时我第一次写这道题的时候内层循环 is:if sum target { res append(res, []int{nums[i], nums[left], nums[right]}) }然后就没有然后了。left 和 right 都不动while 循环永远走不出去直接超时。这个问题看起来蠢但实际写代码时很容易犯因为找到答案后的大脑惯性是处理完了该跳出内层循环了但题目要求找出所有组合不能跳出。正确的做法是找到一组后先做去重然后 left、right-- 同时收缩。为什么两个指针都要动因为当前 left 和 right 的组合已经用过了如果只移动一边另一边保持不变那么新的 sum 只可能远离 target除非数组里有重复值导致的等价组合但我们已经用去重逻辑把这种组合跳过了不可能再找到新答案。所以最合理的下一步就是两边各进一步。4.2 坑二去重写在了错误的位置另一个让我印象深刻的错误是我把去重写在了比较 sum 之前for left right { for left right nums[left] nums[left1] { left } for left right nums[right] nums[right-1] { right-- } // 然后才开始比较 sum }这样写的问题是如果 left 和 right 指向的值刚好凑成 target但你先把 left 移到了最后一个重复值的位置那么你记录的答案就不是第一个出现的组合虽然数值是一样的但记录时机偏晚容易漏掉组合。更重要的是这种去重方式把原本应该在找到答案后执行的逻辑提前到了比较之前导致在 sum ! target 时也做了无意义的去重移动指针位置会乱。正确的位置是在判断 sum target 之后、记录完答案之后立即去重。这样你记录的每一个三元组都是一组等值组合中最早的那个然后通过跳过后面的重复值避免重复记录。4.3 坑三用 map 去重结果内存爆了我还试过一种投机取巧的写法不去严格遵循去重逻辑而是把每个答案三元组排序后转成字符串存进 map[string]bool最后再把 map 里的 key 拆回整数切片返回key : fmt.Sprintf(%d,%d,%d, a, b, c)这个写法在数组规模小的时候能通过但一旦 N 到 3000合法的三元组数量可能达到几十万甚至上百万fmt.Sprintf 的格式化开销加上 map 的存储开销会直接把内存打爆甚至比暴力法还慢。LeetCode 的判题环境对内存有严格限制这种用工具去重的思路在工程上可行但在算法题里是下策。依赖排序去重的双指针写法之所以高效就是因为它不需要任何额外的全局去重结构只在局部做指针移动就能保证结果唯一。这是理解这道题精髓的关键。4.4 对比评测正确写法与错误写法拿一个极端测试用例来对比nums [0, 0, 0, 0, 0, 0]正确结果只有一个三元组 [0, 0, 0]。正确写法输出[[0 0 0]]如果少写了 left/right 去重你可能会得到 6 个甚至更多重复的 [0 0 0]判题直接失败。如果少写了 i 去重外层循环对每个位置的 0 都会跑一遍结果里全是重复的三元组。另一个边界用例nums [-2, 0, 0, 2, 2]。正确结果是 [[-2, 0, 2]]。这里的关键是在找到 [-2, 0, 2] 之后left 指向第一个 0right 指向最后一个 2如果只跳 left 不跳 right或者只跳 right 不跳 left都有可能额外生成重复组合。必须两边都跳到不重复的值才算处理干净。5. 排序 双指针的思路还能怎么用延伸题型5.1 四数之和再加一层循环趁热打铁说说四数之和。它的思路和三数之和完全一致只是需要两层外层循环固定两个数然后内层双指针找另外两个数func fourSum(nums []int, target int) [][]int { sort.Ints(nums) n : len(nums) res : [][]int{} for i : 0; i n-3; i { if i 0 nums[i] nums[i-1] { continue } for j : i 1; j n-2; j { if j i1 nums[j] nums[j-1] { continue } left, right : j1, n-1 sumNeed : target - nums[i] - nums[j] for left right { sum : nums[left] nums[right] if sum sumNeed { res append(res, []int{nums[i], nums[j], nums[left], nums[right]}) for left right nums[left] nums[left1] { left } for left right nums[right] nums[right-1] { right-- } left right-- } else if sum sumNeed { left } else { right-- } } } } return res }复杂度从 O(N^2) 变成了 O(N^3)原理一模一样。Go 语言里要注意 target 可能为负数所以不能像三数之和那样加一个 nums[i] target 的剪枝只能靠重复判断和边界判断来控制。5.2 最接近的三数之和这类题里另一个高频考点是最接近目标值的三数之和。思路也是排序加双指针固定一个数用双指针逼近剩余两个数的和每次计算当前和与 target 的差值保留最小差值。关键是在 sum 大于 target 时 right--小于时 left等于时直接返回 target因为不可能更接近了。这道题不需要去重代码反而更简单。但核心套路是一致的遇到数组里找多个元素满足某种约束的问题排序加双指针是首先要考虑的方案之一。5.3 双指针的适用边界不是所有数组求和问题都适合双指针。比如题目要求返回下标而不是数值排序就会破坏下标信息这时候要优先考虑哈希表。又比如数组本身就是无序且不允许排序的双指针也失效。判断要不要排序的依据是你关心元素的相对顺序吗如果不关心排序加双指针往往是降复杂度的利器。双指针本身的适用条件更苛刻数列必须有序或者至少具备单调性。因为只有大小关系明确时小了就向右、大了就向左才能保证不漏解。一旦缺失这个性质双指针的正确性就要打问号。从三数之和往后看LeetCode 的 Two Pointers 系列基本都是这个框架的变体。掌握了这道题的去重逻辑和指针移动规则后面做三数之和的各个变体、四数之和、盛最多水的容器、接雨水思路都会顺畅很多。我个人的体会是三数之和这道题考察的不是你会不会二分或者你知不知道某个冷门 API而是你能不能把一个 O(N^3) 的暴力问题通过排序将搜索空间压缩成可以夹逼的有序结构同时处理好去重这种工程细节。Go 语言实现的简洁性让这套算法显得非常清爽但简洁的背后需要你对切片、sort 包和循环控制都非常熟悉。建议大家在本地 IDE 里把断点打上用一个重复元素很多的数组逐步运行亲眼观察 left 和 right 的移动过程这比背十遍题解都管用。