okinawa

IT勉強メモ

LeetCodeその3:TwoSum

自分の解答

int配列の中から2つを取り出し、足した値がTargetと同じになる組み合わせを探す問題。

2重ループ。Accept

    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    answer[0] = i;
                    answer[1] = j;
                    
                    return  answer;
                }
            }
        }
        return null;
    }

自分の解答2

HashMap使おうとしたが駄目だったパターン。
求める答えを先に出しておく。

   // HashMapバージョン
    /** 結果はWrong。
     * Target = 6; nums = {3, 1, 3}の場合
     * HashMapに重複するキーを登録してしまうため
     * 
     * あとTarget = 4 nums{2, 1, 3}もだめ。
     * 答え[0, 0] を返す可能性があるため。本来は[1, 2]
     *  **/
    public int[] twoSum2(int[] nums, int target) {
        int[] answerArray = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        
        // 配列をHashMapに格納
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], i); //←同じKeyだと上書きされてしまう
        }
        
        // 1重ループで答え探し
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int answer = target - entry.getKey();
            
            answerArray[0] = map.get(answer);
            answerArray[1] = entry.getValue();
            
            return answerArray;
        }
        return null;
    }

模範解答

重複を避けるテクニックがニクいね!

    // 模範解答
    public int[] twoSum3(int[] nums, int target) {
        HashMap<Integer, Integer> prevMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int diff = target - num;

            if (prevMap.containsKey(diff)) {
                return new int[] { prevMap.get(diff), i };
            }

            prevMap.put(num, i);// ←あとから追加するので重複を避けられる
        }

        return new int[] {};
    }

・引用元

github.com

学んだこと

以前に何かで読んだ気がするのだけど、求める答えがわかっている場合は先に出力しておくと良いっぽい。

今回の場合は answer = Target - num[i] のところ。