題目說明

給定一個整數陣列 nums 和一個整數 target，傳回兩個數字的索引，使它們相加為target。

範例測試資料說明

範例1：

輸入： nums = [2,7,11,15], target = 9
輸出： [0,1]
解釋：因為 nums[0] + nums[1] == 9，所以我們回傳 [0, 1]。

範例2：

輸入： nums = [3,2,4]，target = 6
輸出： [1,2]

範例3：

輸入： nums = [3,3]，taregt= 6
輸出： [0,1]

解法一 : 使用暴力解法

這邊時間複雜度是 O(n²)，如果資料多，會導致很慢

1. 使用雙重迴圈走訪可能的組合
2. 如果 nums[i] + nums[j] 等於目標數值
3. 返回當前 i,j 的索引值

Code 如下:

private int[] twoSum(int[] nums, int target) {
    // 使用雙重迴圈走訪所有可能組合
    // 走訪 nums 陣列
    for (int i = 0; i < nums.length; i++) {
        // 從第 i+1 的索引值開始走訪後面每個元素
        for (int j = i + 1; j < nums.length; j++) {
            // 如果 nums[i] + nums[j] 等於目標數值
            if (nums[i] + nums[j] == target) {
                // 返回當前 i,j 的索引值
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No Solution");
}

解法二 : 使用雜湊表

這邊時間複雜度為 O(n)，相對於暴力解法，是更優的解法。

1. 建立雜湊表 (key 存放數值 , value 存放索引值)
2. 走訪 nums 陣列
3. 計算目標數值和當前數值的差值
4. 如果雜湊表有存在該差值，則返回它們的索引
5. 如果沒有則將當前數值和索引值加入雜湊表
6. 都沒有符合條件的話，則拋出異常

Code 如下:

private int[] twoSum(int[] nums, int target) {
    // 建立雜湊表，用來儲存數字與索引的對應關係 (key 存放數值，value 存放索引值)
    Map<Integer, Integer> map = new HashMap<>();
    // 走訪 nums 陣列
    for (int i = 0; i < nums.length; i++) {
        // 計算目標數值和當前數值的差值
        int difference = target - nums[i];
        // 如果雜湊表存在該差值，表示找到符合條件的兩個數字，並返回它們的索引。
        if (map.containsKey(difference)) {
            return new int[]{map.get(difference), i};
        }
        // 將當前數字和索引加入雜湊表
        map.put(nums[i], i);
    }
    // 如果沒有找到符合條件的兩個數字，則拋出異常
    throw new IllegalArgumentException("No Solution");
}