okinawa

IT勉強メモ

LeetCodeその1:ContainDuplicate

NeetCodeなるものの存在を知ってLeetCodeを始めました。
解説動画がわかりやすくてとても良いです。
英語なので大変ですが。。。

neetcode.io

自分の解答

何も考えずに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;
    }