leetcode15.トリプルの和。

問題

n 個の整数を含む配列 nums が与えられたとき、a + b + c = 0 となるような 3 つの要素 a, b, c が nums に存在するかどうかを判定しなさい。条件を満たし、重複しない3つの要素をすべて求めなさい。

注：回答には重複したトリプルを含めないでください。

例

配列nums = [-1, 0, 1, 2, -1, -4]，
条件を満たすトリプルの集合は以下の通りである：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

アイデア：和が0になる3つの数を見つけること。最初に思いついたのは、i,j,kをループさせて3つの和が0になるかどうかを判定する3重ループでした。しかし、与えられた元の配列は無秩序であり、同じ要素が異なる順序で存在することは間違いありません。そこで、配列を昇順に並べ替えて、[a,b,c]が小さいものから大きいものへと順番に並ぶようにします。ソート後の配列は次のようになります： [-4,-1,-1,0,1,2].

iを0〜長さ2、jをi+1〜長さ1、kをj+1〜長さとします。

var threeSum = function(nums) {
 nums=nums.sort()
 let result=[],now
 for(let i=0;i<nums.length-2;i++){
 if(i===0 || nums[i]!==nums[i-1]){
 for(let j=i+1;j<nums.length-1;j++){
 if(j===i+1 || nums[j]!==nums[j-1]){
 for(let k=j+1;k<nums.length;k++){ 
 if((k===j+1 || nums[k]!==nums[k-1]) && nums[i]+nums[j]+nums[k]===0){
 now=[nums[i],nums[j],nums[k]]
 result.push(now)
 } 
 }
 } 
 }
 }
 }
 return result
};

もう1つ考えるべきケースがあります。ソートが次のように行われた場合、[-4,-1,-1,-1,0,1,2]、i=1,j=2,k=6のときに条件が満たされます。次にj+1,j=3、jの値はまだ-1であり、それでも考慮されるなら、同じ結果[-1,-1,2]が発生します。つまり、i/j/kに遭遇し、最後の値が等しいなら、それをスキップし、最後の値と等しくなくなるまで考慮しません。しかし、この時点でj=i+1/k=j+1であれば、jとi / kとjでの値が等しい場合、これは考慮されます。つまり、3つのループに入るたびに、現在のi / j / kが最初の値であれば下に進むことができるか、現在のi / j / kと前の値が等しくなければ下に進むことができるかを判断しなければなりません。この2つの条件のどちらかが成立すればOKです。

しかし、トリプルループは依然としてO(n3)の時間複雑度を持ち、タイムアウトを示します。

ですから、他の選択肢を考えてみてください：

ダブルポインタ

var threeSum = function(nums) {
 nums=nums.sort((a,b)=>a-b)
 let result=[]
 for(let i=0;i<nums.length-2;i++){
 if(nums[i]>0){break}
 if(i===0 || nums[i]!==nums[i-1]){
 let j=i+1,k=nums.length-1
 while(j<k){
 let sum=nums[i]+nums[j]+nums[k]
 if(sum===0){
 result.push([nums[i],nums[j],nums[k]])
 j++
 while(nums[j]===nums[j-1]){j++}
 k--
 while(nums[k]===nums[k+1]){k--}
 }else if(sum<0){
 j++
 }else{
 k--
 }
 }
 }
 }
 return result
};