NeetCodeなるものの存在を知ってLeetCodeを始めました。
解説動画がわかりやすくてとても良いです。
英語なので大変ですが。。。
自分の解答
何も考えずに2重ループで重複チェック。
タイムオーバーでした。
//配列に重複する数値があるかを調べるプログラム // これだとタイムオーバー public boolean containsDuplicate(int[] nums) { for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { if(nums[i] == nums[j]) { return true; } } } return false; }
模範解答
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> uniques = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (uniques.contains(nums[i])) { return true; } uniques.add(nums[i]); //←ここでaddしているのがグッド } return false; } }
・引用元
github.com
学び
HashSetを使う。
HashSetは順序なし、重複なし。
ランダムアクセスができない。
HashSetは検索の計算量がO(1)。
- ランダムアクセス:まずアクセスする場所を特定して、そこに一発でアクセスするやり方
- シーケンシャルアクセス:端から順番に見ていきながらアクセスする場所を探すやり方
学び2
addする位置を工夫するだけで少しコードがきれいになる。
模範解答のコードは自分だったらこう書いてしまう。
public boolean containsDuplicate3(int[] nums) { Set<Integer> uniques = new HashSet<>(); for (int i = 0; i < nums.length - 1; i++) {//その3.さらに要素数オーバーしないように-1が必要になる uniques.add(nums[i]); //←その1.ifでチェック直前にaddしたくなる if (uniques.contains(nums[i + 1])) { //その2.そうするとここで+1する必要が出てくる return true; } } return false; }