- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
先明确，题目不仅是要求 a + b + c = 0，而且需要三个元素都不重复。
所以我们可以先将数组从小到大排序，排序后，去除重复项会更加简单。
1.外层循环指针 i 遍历数组，题目要求三数之和为 0，考虑此次循环中的数若大于 0，另外两个数肯定也大于 0，则当前位置下无解。
2.去重，如果当前元素和前一个元素相同时，直接跳过即可。
3.内层循环借助双指针夹逼求解，两个指针收缩时也要去除重复的位置。
4.三数之和为 0 时，将当前三个指针位置的数字推入数组即所求。若当前和小于 0 则将左指针向右移动，若当前和大于 0 则将右指针向左移动。
constthreeSum=function(nums){constresult=[]constlen=nums.lengthif(len<3){returnresult}nums.sort((a,b)=>a-b)for(leti=0;i<len-2;i++){if(nums[i]>0){break}if(i>0&&nums[i]===nums[i-1]){continue}letL=i+1letR=len-1while(L<R){letsum=nums[i]+nums[L]+nums[R]if(sum===0){result.push([nums[i],nums[L],nums[R]])while(nums[L]===nums[L+1]){L++}while(nums[R]===nums[R-1]){R--}L++R--}elseif(sum<0){L++}else{R--}}}returnresult}
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)