3Sum — 暴力 O(n³) 到双指针 O(n²)，AI 是怎么把三层循环砍成两层的？

读完本文你将了解3Sum 的暴力→优化→最优完整演进 | 双指针模式为什么是「降复杂度」的本质 | Uber 拼车配对的真实场景 题目原题给你一个整数数组nums返回所有和为 0 的不重复三元组[nums[i], nums[j], nums[k]]i ≠ j ≠ k。项目说明输入nums [-1, 0, 1, 2, -1, -4]输出[[-1,-1,2],[-1,0,1]]约束0 ≤ nums.length ≤ 3000-10⁵ ≤ nums[i] ≤ 10⁵不能返回重复三元组 先问一个问题如果你问 ChatGPT「怎么找三个数加起来等于 0」它大概率不会想「双指针」——第一反应跟大多数人一样三个 for 循环。这不是 AI 笨是问题形态太像「枚举所有组合」了。真正让它和人类一起卡住的不是找三数之和而是去重——你怎么确保不会返回两个一模一样的 [-1, 0, 1] 第一版AI 的朴素解法defthree_sum(nums):nlen(nums)resultset()foriinrange(n):forjinrange(i1,n):forkinrange(j1,n):ifnums[i]nums[j]nums[k]0:result.add(tuple(sorted([nums[i],nums[j],nums[k]])))return[list(t)fortinresult]时间 O(n³)空间 O(k)。1000 个元素就有 1.6 亿次三元组检查10000 个元素就是 160 亿次——直接超时。set 去重是事后补救先把所有组合算出来再去重等于把暴力放大再压缩纯浪费。 AI 的自我优化链第 1 次优化从「枚举三数」变成「枚举两数第三数 -a-b」固定前两个数 a、b第三个数 c -(ab)。用哈希表查 c 是否存在把 O(n³) 降到 O(n²) 平均。但去重还是要 set而且哈希表查找有常数开销实际并不快。第 2 次优化排序 双指针最优解排序后固定第一个数 nums[i]剩下用左右双指针在 nums[i1:] 上找 nums[left] nums[right] -nums[i]。和大了 right 左移和小了 left 右移。一轮 while 就解决了原本两层循环的工作。第 3 次优化排序天然去重排序带来的副产品——相同值相邻。跳过连续重复的 nums[i]、nums[left]、nums[right]不再需要 set。这才是这题真正难的地方去重不是额外步骤而是排序的副产品。暴力三重循环O(n³)哈希表找第三数O(n²) 平均排序 双指针O(n²) 稳定排序天然去重无需 set Python 实现defthree_sum(nums):nums.sort()nlen(nums)result[]foriinrange(n):ifnums[i]0:break# 排序后第一个数已 0后面不可能凑成 0ifi0andnums[i]nums[i-1]:continue# 跳过重复的第一个数left,righti1,n-1whileleftright:totalnums[i]nums[left]nums[right]iftotal0:left1eliftotal0:right-1else:result.append([nums[i],nums[left],nums[right]])whileleftrightandnums[left]nums[left1]:left1whileleftrightandnums[right]nums[right-1]:right-1left1right-1returnresult☕ Java 实现importjava.util.*;publicclassSolution{publicListListIntegerthreeSum(int[]nums){Arrays.sort(nums);ListListIntegerresultnewArrayList();intnnums.length;for(inti0;in;i){if(nums[i]0)break;if(i0nums[i]nums[i-1])continue;intlefti1,rightn-1;while(leftright){inttotalnums[i]nums[left]nums[right];if(total0){left;}elseif(total0){right--;}else{result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}}}returnresult;}}两版代码放一起读者自己对比 Java 和 Python 在排序、边界、结果存储上的差异——比你讲十句都有用。 算法模式拆解双指针模式定义排序后的数组上用一个左指针和一个右指针从两端向中间逼近根据当前值的目标关系决定移动哪一边。适用信号数组/列表求两数之和、三数之和、最接近的值有序或可排序的数据需要「不重复」的组合核心逻辑每轮循环只移动一个指针所以内层是 O(n)。外层枚举第一个数是 O(n)总复杂度 O(n²)。排序后数组-4,-1,-1,0,1,2固定 i-1 (第1个)left-1, right2和-42-2 0left 右移-121 0right 左移-110 ✅记录 [-1,-1,2]left, right--重复此过程...和哈希表方案的对比维度哈希表排序双指针时间O(n²) 平均常数大O(n²) 稳定常数小空间O(n) 哈希表O(1)不计结果去重需要 set事后再处理排序天然去重同步跳过面试评分60 分90 分哈希表方案的问题是它只解决了「找不找得到」没解决「怎么不重复」。排序方案把去重变成了数据结构层面的免费午餐。️ 真实产品场景Uber 三人拼车Uber 拼车系统中有一个经典子问题给定 N 个乘客的实时位置和需求时间窗口找出所有可以同时匹配三人的拼车组合。具体化每个乘客有一个「出发时间偏移值」正数晚出发负数早出发系统需要找到三个乘客出发时间偏差之和等于 0时间窗口完全对齐。这就是 3Sum 的翻版——数组元素是乘客时间偏移找和为 0 的三元组且同一个乘客不能被匹配两次。排序 双指针的优势N10000 时暴力是 O(n³)≈1000亿次双指针是 O(n²)≈1亿次。在拼车系统的实时性要求下这 10000 倍的差距直接决定用户能不能在合理时间内等到车。✅ 面试官的点评通过标准写出排序 双指针 O(n²)正确处理三层去重外层跳重 内层左右双跳重时间 O(n²) 空间 O(1)不计结果加分项nums[i] 0提前 break 的剪枝能说明为什么「排序」是去重的关键——这题的本质不是算法是数据结构设计能推广到 K-SumK4,5…常见踩坑只在外层跳重忘了内层双指针也跳重——返回结果里还是会有重复三元组没做nums[i] 0剪枝——对大数据输入性能退化严重Java 版用new ArrayList(Arrays.asList(...))包裹因为Arrays.asList返回的列表不可修改 同类题推荐题目难度一句话思路Two Sum (LC 1)Easy排序双指针或哈希表4Sum (LC 18)Medium3Sum 外层套一层循环最接近的三数之和 (LC 16)Medium3Sum 改找最接近 target接雨水 (LC 42)Hard双指针取矮边进水量来源说明✅ 已验证LeetCode 15 官方题解 AI 实测 文档/论文《算法导论》第 4 章分治策略