leetcode219. 重複要素が存在する II.

問題

整数の配列と整数 k が与えられたとき、nums [i] = nums [j] となり、i と j の差の絶対値が最大 k となるような、2 つの異なる添字 i と j が配列中に存在するかどうかを判定しなさい。

例1.

 : nums = [1,2,3,1], k = 3
 : true

例2.

 : nums = [1,0,1,1], k = 1
 : true

例3.

 : nums = [1,2,3,1,2,3], k = 2
 : false

解決策1：暴力的解決策

これが最初に思いついたことです。配列を繰り返し処理し、各要素について、その前後のk個のインデックス内にその要素と同じ値を持つ要素があるかどうかを判断し、あればそのままtrueを返し、なければ何もせずに次の要素を繰り返し処理し続けます。

この範囲を半分にして、i〜i＋kの範囲を判定するだけで、左半分に等しい値があれば、それが分かった時点で、前の要素のトラバーサルにあるはずですから、現在の要素までトラバースできるのですから、前のkの現在の要素には、条件を満たすものがないということになります。ですから、判定を繰り返す必要はありません。

var containsNearbyDuplicate = function(nums, k) {
 let j
 for(let i=0;i<nums.length;i++){
 j= i
 while(j<=Math.min(i+k,nums.length-1)){
 if(i!==j && nums[j]===nums[i]){
 return true
 }
 j++
 }
 }
 return false
};

jはスライディングウィンドウの各項目で、iからi+kの範囲ですが、配列のインデックスを超えることはできません。

解決策2：setを使って範囲をコントロール

この問題のキーポイントは、現在の要素のある範囲内になければならない重複要素を見つけることです。重複といえば、セットデータ構造には重複項目はありません。配列をトラバースしながらセットを維持し、各要素をトラバースし、セットの中に同一の要素がなければその要素を入れます。setの中にすでに同じ要素がある場合、それが現在の要素からk個の範囲内にあるかどうかはどのように判断するのでしょうか？また、その範囲をどのように制御するのでしょうか？setのサイズを常にk以下になるように制御することができます。例えば、k=2なら、setの長さを<=2とします。現在の要素を入れた後、毎回長さを判定し、2以上なら、現在のi - kの位置の要素を削除し、setには最大で2つの要素しかないようにします。

これは、setには常に最大2つの要素があるためで、現在の要素iまでトラバースしてsetに同じ値が見つかれば、それはkの範囲内にあることを意味し、直接trueを返します。

var containsNearbyDuplicate = function(nums, k) {
 let set=new Set()
 for(let i=0;i<nums.length;i++){
 if(set.has(nums[i])){
 return true
 }
 set.add(nums[i])
 if(set.size>k){
 set.delete(nums[i-k])
 }
 }
 return false
};

方法1に比べてはるかに短時間。