企业官网建设流程全解析

题目描述

给你一个整数数组 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，-2，2则是一个满足条件的解。

那么一个朴素的想法就是遍历数组，设三个指针i，j，k，首先固定i，j从i+1开始遍历，k则从j+1开始遍历，最内层遍历增加判断if nums[i]+nums[j]+nums[k]==0，先演绎一下，当前i=0，j=1，k=2，判断-5+0+1!=0,k++得k=3,4,5…，如果有满足条件的，则加入到结果数组里。但是这样的可能会导致有重复的结果，因为数组nums里的元素是可以重复的，仅遍历下标不能实现去重。可以考虑在加入results之前新建临时变量，用于判断是否在results之前出现过，如何才能判断呢？最快捷的方法就是先对当前的nums[i],nums[j],nums[k]进行排序，如果不存在在results，则将【排序后】的结果加入，这样也便于下一次的正确“重复判定”。上述思路基本可以通过，但是如果遇到巨大的数组，则会超时，因此需要考虑新的办法，降低计算量。

降低计算量的核心在于如何跳过一些明显就不行的结果。首先终止条件，有一个idea就是判定数组里的最小值如果大于0，则直接返回结果；或者最大值小于0，返回结果；由于此题设定了nums.length最小为3，因此不考虑空数组的情况。这样可以想到，先将数组进行排序如何呢？先sort一下数组（从小到大排序），判定0和n-1的情况。然后依旧设置三指针，i，left，right，这里初始化为i=0，left=i+1,right=n-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[left+1]，即left向前增加1后数值不变，则跳过（执行left++），同理，如果nums[right]==right[right-1]，即right向前减小1后数值不变，则跳过（执行right–）.注意这个过程均还是要保证left<right 的。去掉了这些重复的结果后，再更新left和right。这样就实现了去重，代码如下。

AI总结思路：力扣三数之和 - 解题思路演进全记录

好的！我来帮你完整梳理一下从暴力解法到最终优化版的思路演进过程。

第一阶段：暴力枚举（初始想法）

思路

三重循环枚举所有i < j < k的组合，判断和是否为 0。

代码

foriinrange(n-2):forjinrange(i+1,n-1):forkinrange(j+1,n):ifnums[i]+nums[j]+nums[k]==0:results.append([nums[i],nums[j],nums[k]])

问题

• ❌ 时间复杂度O(n^3)，大数据超时
• ❌ 产生大量重复三元组
• ❌ 三元组顺序不固定

第二阶段：排序 + 去重（初步优化）

思路变化

意识到重复问题，引入排序和not in去重。

关键认知突破

1. 排序可以让三元组有序，方便去重
2. sorted()+not in可以去除重复

代码改进

nums=sorted(nums)# ...triplet=sorted([nums[i],nums[left],nums[right]])iftripletnotinresults:results.append(triplet)

遗留问题

• ❌ 时间复杂度仍然是O(n^3)
• ❌not in去重效率低（每次遍历 results）
• ❌ 没有跳过重复元素，做了大量无用计算

第三阶段：双指针优化（核心突破）

思路转变

这是最重要的认知飞跃：如何从O(n^3)降到O(n^2)？

关键洞察

1. 排序后数组具有单调性
2. 可以用双指针替代内层循环：
   • 固定i
   • left从i+1开始，right从n-1开始
   • 根据三数之和与 0 的比较，移动指针

双指针移动逻辑

ifcurrSum>0:# 和太大 → 需要减小right-=1elifcurrSum<0:# 和太小 → 需要增大left+=1else:# 找到解# 记录结果

复杂度优化

• 从O(n^3)→O(n^2)
• 排序O(n log n)，总体O(n^2)

第四阶段：循环内去重（关键优化）

问题发现

虽然用了双指针，但仍有重复计算：

nums=[-1,-1,-1,0,1,1,1]# 不同位置的相同值会产生重复三元组

解决方案：三层去重

1. 去重i（外层循环）

ifi>0andnums[i]==nums[i-1]:continue# 跳过重复的起点

2. 去重left（找到解后）

whileleft<rightandnums[left]==nums[left+1]:left+=1# 跳过重复的左指针

3. 去重right（找到解后）

whileleft<rightandnums[right]==nums[right-1]:right-=1# 跳过重复的右指针

为什么这样更高效？

• 不需要not in遍历 results
• 在循环层面直接避免产生重复
• 每个有效三元组只被处理一次

第五阶段：剪枝优化（锦上添花）

额外优化点

1. 边界条件

ifn<3ornums[0]>0ornums[-1]<0:return[]

2. 提前终止

ifnums[i]>0:break# 后面的数都更大，不可能和为 0

思路演进图

暴力枚举 (O(n³)) ↓ 发现问题：重复 + 超时 ↓ 排序 + not in 去重 (仍 O(n³)) ↓ 核心突破：双指针思想 ↓ O(n²) 时间复杂度 ↓ 发现问题：仍有重复计算 ↓ 循环内三层去重 ↓ 最终解法：O(n²) + 无重复

关键技术点总结

重要认知转变

1. 从"事后去重"到"事前避免"

   • 之前：先产生重复，再用not in去除
   • 之后：在循环层面直接跳过重复值

2. 从"盲目枚举"到"智能移动"

   • 之前：固定所有指针，逐个尝试
   • 之后：利用有序性，根据和的大小动态移动

3. 从"全部计算"到"提前终止"

   • 之前：所有循环都执行完
   • 之后：利用nums[i] > 0提前退出

这就是你从暴力解法到最优解的完整思考历程！每一步都有明确的问题驱动和解决方案，是非常好的学习路径。🚀

代码

classSolution:defthreeSum(self,nums:list[int])->list[list[int]]:results=[]nums=sorted(nums)n=len(nums)ifnums[0]>0ornums[-1]<0:returnresultsforiinrange(0,n-2):ifi>0andnums[i]==nums[i-1]:continue# 去重逻辑1ifnums[i]>0:break# 这一点没想到left=i+1right=n-1while(left<right):currSum=nums[i]+nums[left]+nums[right]ifcurrSum>0:right-=1elifcurrSum<0:left+=1else:results.append([nums[i],nums[left],nums[right]])while(left<right)andnums[right]==nums[right-1]:right-=1# 去重逻辑2while(left<right)andnums[left]==nums[left+1]:left+=1# 去重逻辑3left+=1# 这里是更新指针right-=1returnresults