leetcode三数の和(js実装)

2016 ワード

この問題はleetcodeから来て、以下はテーマです.
n個の整数を含む配列numsが与えられ、a+b+c=0となるように、numsに3つの要素a,b,cが存在するか否かが判断される.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
  ,      nums = [-1, 0, 1, 2, -1, -4],

           :
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析:もともと2層forサイクルとして用いられていたが、311番目のテストでは、テスト例が長すぎてタイムアウトしたため、実現方法が変更された.
(1)、配列を並べ替え、配列の最初の要素が0より大きい場合、または最後の要素が0より小さい場合、0となることはあり得ない.
(2)、まず1つの要素(A)を選択し、2つのポインタを利用して配列の要素を遍歴し、1つのポインタをA要素の後の要素(B)に、もう1つのポインタは配列の最後の要素(C)を指す.
(3)、B+Cの結果がAの逆数であるか否かを判断し、B+C>(-A)であればCポインタを前へ移動させ、B+Cであれば
(4)、Bポインタの要素が前の要素と等しい場合、Bポインタは1ビット後ろに移動し、Cポインタが後の要素と等しい場合、Cポインタは1ビット前に移動する.
コードの例を次に示します.
/**  * @param {number[]} nums  * @return {number[][]}  */var threeSum = function(nums) {     var result = new Array();     var len = nums.length;     var flag = 0;     var hash = {};     nums.sort((a, b) => {         return a-b;     });     if(nums[0] > 0 || nums[len - 1] < 0) return result;     for(var i = 0; i < len; i++){         if(nums[i] === nums[i-1]) continue;         flag = 0 - nums[i];         var start = i + 1, end = len - 1;         while(start < end){             var middle = new Array();             if(nums[start] + nums[end] < flag){                 start++;             } else if(nums[start] + nums[end] > flag){                 end--;             } else {                 middle.push(nums[i]);                 middle.push(nums[start]);                 middle.push(nums[end]);                 if(!hash[middle]){                     hash[middle] = true;                     result.push(middle);                 }                 start += 1;                 end -= 1;                 while(start < end && nums[start] === nums[start - 1]){                     start += 1;                 }                 while(start < end && nums[end] === nums[end + 1]){                     end -= 1;                 }             }         }     }     return result; };