Two Sum は Leetcode を始める人が最初に解く定番の問題です。以前に解いたことはありましたが、自分の思考プロセスをきちんと言語化したくて、改めて記事にまとめました。では始めましょう。

Two Sum

問題の説明

配列 nums と整数 target が与えられます。足し合わせると target になる 2 つの要素のインデックスを返してください。解は必ず 1 つ存在することが保証されています。

解法

Solution 1

まず思いつくのはブルートフォースです。2 重ループで全ての組み合わせを試し、条件を満たした時点で即座に return します。Java の実装は以下のとおりです。

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

問題は解けますが、時間計算量は O(n²) です。最悪の場合、約 n²/2 回の比較が発生します。空間計算量は O(1) で、追加のデータ構造は使用していません。

Solution 2

最適解は HashMap を使う方法で、時間計算量を O(n²) から O(n) に下げられます。考え方は、各要素の値とインデックスをマップに記録し、現在の要素を処理するたびに補完値（target - nums[i]）がマップに存在するか確認するというものです。存在すれば、ペアが見つかったことになります。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        if (!map.containsKey(target - nums[i])) {
            map.put(nums[i], i);
        } else {
            return new int[]{map.get(target - nums[i]), i};
        }
    }
    return new int[]{-1, -1};
}

時間計算量：O(n)（各要素を 1 回だけ走査）。空間計算量：O(n)（最悪の場合、n 件全てをマップに格納）。

まとめ

Two Sum はシンプルな問題ですが、いくつかの重要な概念を含んでいます。

• ブルートフォースと最適解の違い
• HashMap の検索特性
• 空間を使って時間を節約するトレードオフ
• 時間計算量の分析

だからこそ、Leetcode 最定番の入門問題とされているのです。

Two Sum の本質は「2 つの数を探す」のではなく、「すでに見た数を記憶し、その『もう片方』を探す」ことにあります。この考え方は多くの問題に応用できます。

Remove Duplicates from Sorted Array

問題の説明

昇順にソートされた配列が与えられます。配列をその場で操作し、先頭の k 個が重複のない有序な要素になるようにして、k を返してください。

解法

Solution 1

1 つのループで配列を走査しながら、重複カウンター duplicates（初期値 0）を管理します。現在の要素が前の要素と同じなら重複なのでカウンターを増やします。各要素をカウンター分だけ左にずらして書き込み、最終的な長さは nums.length - duplicates です。

public int removeDuplicates(int[] nums) {
    int duplicates = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            duplicates++;
        }
        nums[i - duplicates] = nums[i];
    }
    return nums.length - duplicates;
}

Solution 2

fast/slow の 2 ポインタを明示的に使う、より簡潔な書き方です。slow ポインタは新しい一意の要素が見つかった時だけ進みます。

public int removeDuplicates(int[] nums) {
    int slow = 1;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

まとめ

どちらも時間計算量 O(n)、空間計算量 O(1) です。

2 つの解法の核心は同じで、「次に書き込む有効な位置」をポインタで追跡するというものです。違いは Solution 1 が重複数をオフセットとして使うのに対し、Solution 2 は fast/slow を明示的に扱う点です。面試では Solution 2 の方が意図が伝わりやすく、こちらを優先することをお勧めします。

Best Time to Buy and Sell Stock

問題の説明

各要素が株価を表す配列が与えられます。1 回の売買で得られる最大利益を計算してください。

解法

利益を最大化するには、これまでの最小価格を記録しながら、現在の価格との差が最大になるタイミングを追跡します。

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        int profit = price - minPrice;
        maxProfit = Math.max(maxProfit, profit);
    }
    return maxProfit;
}

まとめ

時間計算量：O(n)。空間計算量：O(1)。

Best Time to Buy and Sell Stock の本質は、全ての買い売り組み合わせを列挙する必要がないことです。配列を 1 度走査しながら「現在の最安値」を維持するだけで、O(n) で最大利益を求められます。