LeetCodeのEasy問題をJavaで解説 #1【Two Sum】

Two Sum

LeetCodeのEasy問題をJavaで解説します。
今回の問題はTwo Sumです。

⭐️問題文

原文

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

日本語訳

整数配列numsと整数targetが与えられたときnums内の要素のうち、合計がtargetになる2つの値のインデックスを返してください。

各入力には必ず1つの解が存在し、同じ要素を2回使用することはできません。

返却するインデックスの順序は問いません。

⭐️入出力例

例1

• 入力：nums = [2, 7, 11, 15], target = 9
• 出力：[0, 1]
• 解説：nums[0] +　nums[1] = 2 + 7 = 9となるため、[0, 1]を返します。

例2

• 入力：nums = [3, 2, 4], target = 6
• 出力：[1, 2]

例3

• 入力：nums = [3, 3], target = 6
• 出力：[0, 1]

⭐️制約

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 解は常にただ1つだけ存在します。

⭐️最初に思いつく方法

まず、すべてのペアを試す方法（全探索）が考えられます。

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

🔻問題点

• 2重ループですべてのペアを試すため、時間がかかる
• 時間計算量はO(n²)

補数（complement）を考える

ある数字numに対して、target - numがもう一方の数（補数）になります。

target = 9
num = 2
補数 = 9 - 2 = 7

つまり、補数（complement） を先に求めればいいのです。

int complement = target - nums[i]; 

HashMapを使って効率化する

HashMapを使って、「必要な数（target - num）」がすでに登録されているか を調べます。

if (map.containsKey(complement)) { // 補数がMapに登録されているか確認する
    return new int[] {map.get(complement), i}; // 補数のインデックスと現在のインデックスを返す
}
map.put(nums[i], i); // 現在の値とインデックスをMapに登録する

⭐️解答例

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] {map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[] {};
    }
}

✅改善点

• 補数の考え方とHashMapの活用によって高速に解を求められる
• 時間計算量はO(n)

⭐️まとめ

Two Sumは、一見すると全探索で解けるシンプルな問題ですが、補数の考え方とHashMapの活用により、計算量を大幅に削減することができます。
小さな工夫で大きくパフォーマンスが変わることを実感していただけたと思います。