leetcode三数の和(js実装)
2016 ワード
この問題はleetcodeから来て、以下はテーマです.
n個の整数を含む配列
注意:答えに重複する三元グループは含まれてはいけません.
分析:もともと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; };
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; };