LeetCode Note Java 00167：Two Sum II - Input Array Is Sorted

給定一排序過的 int Array 與 1 目標值，找出 Array 中相加為目標值的兩個數的索引。其中所引從 1 開始，限制同一元素不得使用兩次，限制只能使用恆定的額外空間。

題目

Two Sum II - Input Array Is Sorted Medium

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

解法

直觀的拿之前 00001：Two Sum 的解法來用：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> diffMap = new HashMap<>(); // diff, index
        for (int i = 0; i < numbers.length; i++) {
          int value = numbers[i];
          if (diffMap.containsKey(value)) {
            return new int[] {diffMap.get(value) + 1, i + 1}; // 限制索引從 1 開始所以要 +1
          } else {
            diffMap.put(target - value, i);
          }
        }
        return null;
    }
}

雖然這樣通過了 leetCode Submit，但應該不符合題目要求的 只使用恆定額外空間。

Two Pointer 方法：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (numbers[l] + numbers[r] != target) {
          if (numbers[l] + numbers[r] > target) {
            r--;
          } else {
            l++;
          }
        }
        return new int[] {l + 1, r + 1}; // 限制索引從 1 開始所以要 +1
    }
}

檢討

之後知道排序過的 Array 可以用 two pointer 的方式。