題目說明

這題目和第一題非常像：[LeetCode] 1. Two Sum

陣列已經按照從小到大的順序排好了，現在要找到其中兩個數字，使它們的和等於一個特定的目標數字。

而且你需要返回這兩個數字的位置（索引），這裡的位置是從1開始算的。

題目連結：LeetCode - Two Sum II

範例測試資料說明

範例 1：

輸入：numbers = [2,7,11,15]，target = 9
輸出：[1,2]
解釋：2 與 7 的和為 9。
因此，index1 = 1，index2 = 2。
我們返回 [1, 2]。

範例2：

輸入：numbers = [2,3,4]，target = 6
輸出：[1,3]
解釋：2 與 4 的和為 6。
因此，index1 = 1，index2 = 3。
我們返回 [1, 3]。

範例3：

輸入：numbers = [-1,0]，target = -1
輸出：[1,2]
解釋：-1 與 0 的和為 -1。
因此，index1 = 1，index2 = 2。
我們返回 [1, 2]。

解法一 : 使用暴力解法

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

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

Code 如下:

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

解法二 : 使用雜湊表

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

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

Code 如下:

private int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        int diff = target - numbers[i];
        if (map.containsKey(diff)) {
            return new int[]{map.get(diff) + 1, i + 1};
        }
        map.put(numbers[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

解法三 : 使用雙指針

1. 先定義兩個指針 left 和 right ，分別指向陣列的開頭和結尾。
2. 接著使用 while ，不斷判斷兩個指針的所指的數字是否符合目標數
3. 在 while 迴圈中，如果目前兩個指針所指的數字之和小於目標值，我們將左指針 left 往右移動一位，因為在這種情況下，我們需要增加兩個數字的和，所以需要更大的數字參與計算，
4. 否則，如果目前兩個指針所指的數字之和大於目標值，我們將右指針 right 往左移動一位，因為在這種情況下，我們需要減少兩個數字的和，所以需要更小的數字參與計算。
5. 最後如果有找到，則返回當前 left+1, right+1 的索引

Code 如下:

private int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (numbers[left] + numbers[right] != target) {
        if (numbers[left] + numbers[right] < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{left + 1, right + 1};
}