题目描述给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。个人思路假如有一个数组[-5,0,1,2.-2,3,6,-8,4],很明显这里的0-22则是一个满足条件的解。那么一个朴素的想法就是遍历数组设三个指针ijk首先固定ij从i1开始遍历k则从j1开始遍历最内层遍历增加判断if nums[i]nums[j]nums[k]0先演绎一下当前i0j1k2判断-501!0,k得k3,4,5…如果有满足条件的则加入到结果数组里。但是这样的可能会导致有重复的结果因为数组nums里的元素是可以重复的仅遍历下标不能实现去重。可以考虑在加入results之前新建临时变量用于判断是否在results之前出现过如何才能判断呢最快捷的方法就是先对当前的nums[i],nums[j],nums[k]进行排序如果不存在在results则将【排序后】的结果加入这样也便于下一次的正确“重复判定”。上述思路基本可以通过但是如果遇到巨大的数组则会超时因此需要考虑新的办法降低计算量。降低计算量的核心在于如何跳过一些明显就不行的结果。首先终止条件有一个idea就是判定数组里的最小值如果大于0则直接返回结果或者最大值小于0返回结果由于此题设定了nums.length最小为3因此不考虑空数组的情况。这样可以想到先将数组进行排序如何呢先sort一下数组从小到大排序判定0和n-1的情况。然后依旧设置三指针ileftright这里初始化为i0lefti1,rightn-1.那么在i的循环内部移动left和right来判断结果(这里循环应该用while结构)。可以想到的是如果nums[i]nums[left]nums[right]0,说明当前需要减小某些值则right–如果三数之和小于0则需要增加left.如果正好满足条件则可以考虑在这里加入前面的去重逻辑将结果加入results。遍历结束后返回results。上一段的新思路还可以但是经过测试依旧会超时主要是在判断去重的逻辑代码。每一次都要遍历一遍results因此可以考虑到将去重逻辑加入到每一次循环里。首先对于指针i如果nums[i]nums[i-1]那么可以跳过当前i了。这样足够了吗经过验证这样还是不够因此指针i的重复性排除了但是left和right依旧没排除更新指针i后判定当前结果的大小大于0则right–小于0则left,等于0则将结果加入results并且还要继续更新left和right这里加入去重逻辑如果nums[left]nums[left1]即left向前增加1后数值不变则跳过执行left同理如果nums[right]right[right-1]即right向前减小1后数值不变则跳过执行right–.注意这个过程均还是要保证leftright 的。去掉了这些重复的结果后再更新left和right。这样就实现了去重代码如下。AI总结思路力扣三数之和 - 解题思路演进全记录好的我来帮你完整梳理一下从暴力解法到最终优化版的思路演进过程。第一阶段暴力枚举初始想法思路三重循环枚举所有i j k的组合判断和是否为 0。代码foriinrange(n-2):forjinrange(i1,n-1):forkinrange(j1,n):ifnums[i]nums[j]nums[k]0:results.append([nums[i],nums[j],nums[k]])问题❌ 时间复杂度O(n^3)大数据超时❌ 产生大量重复三元组❌ 三元组顺序不固定第二阶段排序 去重初步优化思路变化意识到重复问题引入排序和not in去重。关键认知突破排序可以让三元组有序方便去重sorted()not in可以去除重复代码改进numssorted(nums)# ...tripletsorted([nums[i],nums[left],nums[right]])iftripletnotinresults:results.append(triplet)遗留问题❌ 时间复杂度仍然是O(n^3)❌not in去重效率低每次遍历 results❌ 没有跳过重复元素做了大量无用计算第三阶段双指针优化核心突破思路转变这是最重要的认知飞跃如何从O(n^3)降到O(n^2)关键洞察排序后数组具有单调性可以用双指针替代内层循环固定ileft从i1开始right从n-1开始根据三数之和与 0 的比较移动指针双指针移动逻辑ifcurrSum0:# 和太大 → 需要减小right-1elifcurrSum0:# 和太小 → 需要增大left1else:# 找到解# 记录结果复杂度优化从O(n^3)→O(n^2)排序O(n log n)总体O(n^2)第四阶段循环内去重关键优化问题发现虽然用了双指针但仍有重复计算nums[-1,-1,-1,0,1,1,1]# 不同位置的相同值会产生重复三元组解决方案三层去重1. 去重i外层循环ifi0andnums[i]nums[i-1]:continue# 跳过重复的起点2. 去重left找到解后whileleftrightandnums[left]nums[left1]:left1# 跳过重复的左指针3. 去重right找到解后whileleftrightandnums[right]nums[right-1]:right-1# 跳过重复的右指针为什么这样更高效不需要not in遍历 results在循环层面直接避免产生重复每个有效三元组只被处理一次第五阶段剪枝优化锦上添花额外优化点1. 边界条件ifn3ornums[0]0ornums[-1]0:return[]2. 提前终止ifnums[i]0:break# 后面的数都更大不可能和为 0思路演进图暴力枚举 (O(n³)) ↓ 发现问题重复 超时 ↓ 排序 not in 去重 (仍 O(n³)) ↓ 核心突破双指针思想 ↓ O(n²) 时间复杂度 ↓ 发现问题仍有重复计算 ↓ 循环内三层去重 ↓ 最终解法O(n²) 无重复关键技术点总结阶段核心思想关键代码解决的问题1三重循环for i, j, k基础枚举2排序去重sorted()not in去除重复三元组3双指针left/right--时间复杂度从 O(n³) 降到 O(n²)4循环内去重跳过重复的 i, left, right避免 not in 的低效查找5剪枝优化边界条件 提前终止减少无效计算重要认知转变从事后去重到事前避免之前先产生重复再用not in去除之后在循环层面直接跳过重复值从盲目枚举到智能移动之前固定所有指针逐个尝试之后利用有序性根据和的大小动态移动从全部计算到提前终止之前所有循环都执行完之后利用nums[i] 0提前退出这就是你从暴力解法到最优解的完整思考历程每一步都有明确的问题驱动和解决方案是非常好的学习路径。代码classSolution:defthreeSum(self,nums:list[int])-list[list[int]]:results[]numssorted(nums)nlen(nums)ifnums[0]0ornums[-1]0:returnresultsforiinrange(0,n-2):ifi0andnums[i]nums[i-1]:continue# 去重逻辑1ifnums[i]0:break# 这一点没想到lefti1rightn-1while(leftright):currSumnums[i]nums[left]nums[right]ifcurrSum0:right-1elifcurrSum0:left1else:results.append([nums[i],nums[left],nums[right]])while(leftright)andnums[right]nums[right-1]:right-1# 去重逻辑2while(leftright)andnums[left]nums[left1]:left1# 去重逻辑3left1# 这里是更新指针right-1returnresults