目次
解いた問題
leetcode 219. Contains Duplicate II
整数配列numsと整数kが与えられるので、配列内の異なるインデックス iとjに対して下記条件を満たすときTrue、そうじゃないときFalseを返してねって問題。
- `nums[i] == nums[j]
|i - j| <= k
値が同じで、なおかつインデックス差がk以下であるかを判定する必要がある。
学び
- スライディングウィンドウという新しいアルゴリズムを知れた
- 「早期終了」をするための境界条件を意識するとより洗練されたコーディングに繋がりそう
- 値をすべて持つ、という考えはアンチパターンチックになりがちだと反省
最初に考えた解法
先日の学びから重複はsetを使ったほうが筋がいいかなと考えた。
先日解いた重複問題は下記。
https://zenn.dev/zenn_mita/articles/ad9409e7e0d853
ただ今回は重複だけでなくインデックス差を見る必要があるので、バリューにインデックスを保持して計算に使用できるdictを使ったほうがいいと判断。
はじめて出てきた整数をキー、インデックスをバリューとしてdictに保存し、2回目以降に出てきたらインデックス差を計算、k以下ならTrue返却、以上なら後に出てきたインデックスを保存して繰り返す、という流れを作ればいいのではと考え実装。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
hashmap = {}
for i, num in enumerate(nums):
if num not in hashmap:
hashmap[num] = i
else:
diff = i - hashmap[num]
if k >= diff:
return True
else:
hashmap[num] = i
return False
上記で一発正解。よ～しよしよし。
hashmap[num] = iという処理を2回記載しているのが少し気になってはいる。
ソフトウェア開発原則の一つにDRY原則、Don’t Repeat Yourselfというものがあり、同じ処理を繰り返すことは悪とされがち。
最初の分岐でor条件を使って実現できるのかな？それでも時間・空間計算量は変わらず$O(n)$になっているな、などと思いつつ正解を見ることに。
正解
今回は回答が2つ出てきた。
まず私の回答をより洗練させたものが下記。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
last = {} # value -> last index
for i, x in enumerate(nums):
j = last.get(x)
if j is not None and i - j <= k:
return True
last[x] = i
return False
差分はhashmapをlast index用と明記して使用している点と、それを利用してdiffを排除し処理を単純化しているところでしょうか。
懸念点である重複処理をなくし、dictへのアクセスを1回だけにすることで単純化を成功させています。
dict.get(x)は指定したキーに対応する「値（value）」を取得するためのメソッドで、最後に出現したインデックスを簡単に取れるようになっています。
dict[x]だとキーが存在しないときにKeyErrorになりますが、.getだとNoneが返りエラーにならないため、値の存在確認とkの条件を一気に判定することができます。
ちなみにhashmapという命名だと含意が広すぎるためやめたほうがいいそうです。
2つ目の回答が下記。
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
window = set()
for i, x in enumerate(nums):
if x in window:
return True
window.add(x)
if i >= k:
window.remove(nums[i - k])
return False
これは「スライディングウィンドウ」というアルゴリズムを使用した解法。
スライディングウィンドウとは、連続区間（window）を一定ルールで前に滑らせながら処理する手法のこと。
今回だとsetの要素数がk以上になった時にはじく、というウィンドウを作っている。
一瞬window.add(x)で値を入れて、window.remove(nums[i - k]でインデックスを排除している？と勘違いしましたが、nums[i - k]で入力であるnumsを参照してウィンドウサイズから外れた値をsetから排除しているのだと気づきました。
スライディングウィンドウの一番のメリットはメモリ使用量削減でしょうか。
hashmapを使用するアルゴリズムでは空間計算量が$O(n)$だったのに対して、スライディングウィンドウを使用するとウィンドウサイズkが展開されるため、$O(k)$で収まります。
入力が大きいときに効果を発揮しそうです。
感想
既知のアルゴリズムを使用して正解できたこと、未知のアルゴリズムを知れたことが今回の収穫です。
やはり「なぜそう動くのか」という原理を理解しながらコーディングするのは面白いですね。
今後のキャリアに効くような気付きも得られるし単純に面白いしで、leetcodeを初めてよかったなと考えています。
引き続きちょくちょく進めていきます。