leetcode题目

自己的原先暴力解法

自己的题解(全部超时):

  1. /**
  2. * @param {number[]} nums
  3. * @return {number[][]}
  4. */
  5. var threeSum = function(nums) {
  6.   const sumArr = [];
  7.   if(nums.length<3){
  8.     return []
  9.   }
  11.   // 暴力 超时
  12.   // let len = nums.length;
  13.   // for(let i = 0 ; i < len ; i++ ){
  14.   //     for(let j = i +1 ; j < len ; j++ ){
  15.   //         for(let z = j + 1 ; z < len ; z++ ){
  16.   //             if(nums[i] + nums[j] + nums[z] === 0 && [nums[i] , nums[j] , nums[z]].sort()){
  17.   //                 let sum = [nums[i] , nums[j] , nums[z]].sort()
  18.   //                 if(sumArr.every(c=>`${c}`!==`${sum}`))
  19.   //                 sumArr.push(sum)
  20.   //             }
  21.   //         }
  22.   //     }
  23.   // }
  25.   // 暴力,不让过
  26.   //     const _nums = nums.sort((a,b)=>a-b);//排序
  27.   //     const len = _nums.length
  28.   //     console.log(_nums,len);
  29.   //     let maxIndex = len - 1;
  31.   //     for(let i = 0 ; i < len-2 ; i++ ){
  34.   //         if(_nums[i]>0){
  36.   //             break  
  37.   //         }
  38.   //          if(_nums[i]+_nums[maxIndex -1] +_nums[maxIndex ]<0){
  39.   //                 continue
  40.   //             }
  41.   //         for(let j = i + 1; j < len-1 ; j++ ){
  44.   //             if(_nums[i]+_nums[j] > 0 ){
  46.   //                break
  47.   //             }
  48.   //             if(_nums[i]+_nums[j] +_nums[maxIndex ]<0){
  49.   //                 continue
  50.   //             }
  51.   //             for(let z = j +1 ; z < len ; z++ ){
  54.   //                 if(_nums[i] + _nums[j] + _nums[z] > 0 ){
  55.   //                    break
  56.   //                 } 
  57.   //            if(_nums[i] + _nums[j] + _nums[z] === 0 ){
  58.   //                let sum = [_nums[i] , _nums[j] , _nums[z]] 
  59.   // if(sumArr.every(c=>`${c}`!==`${sum}`))
  60.   //                     sumArr.push(sum)
  61.   //            }
  62.   //             }
  63.   //         }
  65.   //     }
  67.   // 
  69.   const _nums = nums.sort((a,b)=>a-b);//排序
  70.   const len = _nums.length;
  71.   const arr1 = {}
  72.   for(let i = 1;i < len - 1 ; i++ ){
  73.     for(let j = len - 1;j > i ; j-- ){
  74.       const sum = _nums[i] +_nums[j]
  75.       // console.log(sum,i,j,_nums[i] ,_nums[j])
  76.       if(sum<0){
  77.         break;
  78.       }
  79.       let arr = arr1[sum];
  80.       const key= `${[_nums[i],_nums[j]]}`
  81.       if(arr){
  82.         // if(_nums[i]===_nums[arr[len1-1][0]]&&_nums[j]===_nums[arr[len1-1][1]]&&)
  83.         arr[key] = [i,j]
  84.       }else {
  85.         arr1[sum] = {[key]:[i,j]}
  86.       }
  87.     }
  88.   }
  89.   console.log(arr1,_nums)
  90.   for(let i = 0;i < len - 2 ; i++ ){
  91.     const first = arr1[-_nums[i]]
  92.     if(first ){
  93.       for(let k in first){
  94.         const c= first[k]
  95.         if(c[0]>i){
  96.           const a = [_nums[i]].concat(c.map(cc=>_nums[cc]))
  97.           if(sumArr.every(c=>`${c}`!==`${a}`))
  98.             sumArr.push(a)
  99.         }
  100.       }
  104.       // arr1[-_nums[i]].forEach(c=>{
  105.       //     if(c[0]>i){
  106.       //         const a = [_nums[i]].concat(c.map(cc=>_nums[cc]))
  107.       //         if(sumArr.every(c=>`${c}`!==`${a}`))
  108.       //         sumArr.push(a)
  109.       //     }
  110.       // })
  111.     }
  112.   }
  113.   return sumArr
  114. };

双指针

「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2)减少至 O(N)O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)

正确的解法

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var threeSum = function(nums) {
  6.     let sumArr = [];
  8.     if(nums.length<3){
  9.         return []
  10.     }
  11.     // 全是0过不了
  12.     if(Array.from(new Set(nums)).length===1&&nums[0]===0){
  13.         return [[0,0,0]]
  14.     }
  16.     // 暴力 超时
  17.     let len = nums.length;
  18.     const _nums = nums.sort((a,b)=>a-b);//排序
  19.     for(let i = 0 ; i < len - 2 ; i++ ){
  21.         if(_nums[i]>0){
  22.             break
  23.         }
  24.         if(_nums[i]+_nums[len - 2] +_nums[len - 1 ]<0){
  25.                 continue
  26.             }
  27.         for(let j = i +1 ; j < len - 1; j++ ){
  28.             if(_nums[i]+_nums[j] >0){
  29.                 break;
  30.             }
  31.              if(_nums[i]+_nums[j] +_nums[len - 1 ]<0){
  32.                 continue
  33.             }
  34.             let preZ = len - 1
  35.             for(let z = len - 1 ; z > j ; z-- ){
  37.                 if(_nums[i] + _nums[j] + _nums[z] === 0 ){
  38.                     let sum = [_nums[i] , _nums[j] , _nums[z]] 
  39.                     // if(sumArr.every(c=>`${c}`!==`${sum}`))
  40.                     sumArr.push(JSON.stringify(sum));
  42.                     preZ = z - 1;
  43.                     // while(_nums[preZ]===_nums[z]){
  44.                     //     preZ--
  45.                     // }
  46.                     break
  47.                 }
  48.             }
  49.         }
  50.     }
  51. sumArr = Array.from(new Set(sumArr)).map(c=>JSON.parse(c))
  55.     return sumArr
  56. };