15. 三数之和

[blueWind123731]

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

[blueWind123731]

时间复杂度：O(n²) 空间复杂度：O(1)

1.数组排序 2.去重 3.双指针

function threeSum (nums) {
     let result = [];
     nums.sort((a,b)=>a-b)
     if(nums.length<3){
         return result
     }
     for(let i=0;i<nums.length-2;i++){
         if(nums[i]>0){
             break
         }
         if(i>0&&nums[i]===nums[i-1]){
             continue
         }
         const target = 0-nums[i]
         let l = i+1
         let r = nums.length-1
         while(l<r){
             if(nums[l]+nums[r]>target){
                 r--
             }else if(nums[l]+nums[r]<target){
                 l++
             }else {
                 result.push([nums[i],nums[l],nums[r]])
                 l++
                 r--
                 while(l<r&&nums[l]===nums[l-1])l++
                 while(l<r&&nums[r]===nums[r+1])r--
             }
         }
     }
     return result  
};  

[blueWind123731]

时间复杂度：O(n²) 空间复杂度：O(1)

1.数组排序 2.去重 3.hash

function threeSum(nums){
let result = []
     nums.sort((a,b)=>a-b)
     if(nums.length<3){
         return result
     }
     for(let i=0;i<nums.length-1;i++){
         if(nums[i]>0){
             break
         }
         if(i>0&&nums[i]===nums[i-1]){
             continue
         }
         const target = 0-nums[i]
         let map = new Map()
         for(let j=i+1;j<nums.length;j++){
             if(result.length){
                 if(result[result.length-1][1]===target-nums[j]||result[result.length-1][2]===nums[j]){
                     continue
                 }
             }
             if(typeof map.get(nums[j])==='number'){
                 result.push([nums[i],map.get(nums[j]),nums[j]])
             }
             map.set(target-nums[j],nums[j])
         }
     }
     return result
}