【每日一题】LeetCode 15. 三数之和 TypeScript

给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]输出：[[0,0,0]]解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

function threeSum(nums: number[]): number[][] { const three:number[][] = [] nums.sort((a,b)=>a-b) for(let i=0;i<nums.length-2;i++){ if(i>0 && nums[i]===nums[i-1]) continue let j=i+1 let z=nums.length-1 while(j<z){ const sum = nums[i]+nums[j]+nums[z] if(sum===0){ three.push([nums[i],nums[j],nums[z]]) while(j<z&&nums[j]===nums[j+1]) j++ while(j<z&&nums[z]===nums[z-1]) z-- j++ z-- }else if(sum>0){ z-- }else{ j++ } } } return three };

如果用暴力解法，三层循环时间复杂度是O(n³)，这个算法的目的就是降低时间复杂度+去重

①为什么排序？使重复的值相邻，可以更好地跳过：数组.sort((a,b)=>a-b) 从小到大，升序

②去重：如果下一个值和上一个值相同，直接跳过，i++/j++/z++

注释版：

function threeSum(nums: number[]): number[][] { //初始化声明二维数组，数组嵌套数组 const three:number[][] = [] //从小到大拍寻 nums.sort((a,b)=>a-b) //i是第一个数的下标 //i<length-2 判断条件，比如length=5,i<3,i的值是0,1,2 取不到3 //给j、z腾两个位置 for(let i=0;i<nums.length-2;i++){ //如果重复，continue跳过下面步骤，直接i++ if(i>0 && nums[i]===nums[i-1]) continue //定义一个左指针 let j=i+1 //定义一个右指针 let z=nums.length-1 //两个指针的不重合且一个在左一个在右 while(j<z){ const sum = nums[i]+nums[j]+nums[z] if(sum===0){ //满足条件就push末尾添加 three.push([nums[i],nums[j],nums[z]]) //如果重复，再走一遍循环也是=0，j++移到最后一个相同的值的下标 while(j<z&&nums[j]===nums[j+1]) j++ //z同理 while(j<z&&nums[z]===nums[z-1]) z-- //以上步骤都是j和z都指向相同值得最后一个下标 //指针需要继续移位查找更多的组合 j++ z-- //如果和大了，证明需要更小的数，右指针需要往前移 }else if(sum>0){ z-- //如果和小了，证明需要更大的数，左指针需要往前移 }else{ j++ } } } return three };

共勉，祝天下考生旗开得胜！