LeetCode 167. Two Sum II - Input Array Is Sorted

Two Sum的變化題，輸入的陣列參數為已排序的整數。

題目

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.

Example 1:

  Input: numbers = [2,7,11,15], target = 9
  Output: [1,2]
  Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

  Input: numbers = [2,3,4], target = 6
  Output: [1,3]
  Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

  Input: numbers = [-1,0], target = -1
  Output: [1,2]
  Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

先想到的解法

之前寫過Two sum的題目，所以應該不會再用一樣的方式解。想到用一個while廽圈兩個索引一個由陣列前往後、一個由後往前遍歷直到索引相交。前後元素相加若大於target則後索引往前移動；若前後元素相加小於target則前索引往前移動。時間複雜度應該是O(n)。

nums=[2,7,11,15], target=[9]
L1:=================================================================
               v (i=nums.length - 1)
  nums=[2,7,11,15]  
        ^ (j=0)

L2:=================================================================
            v (i=nums.length - 2)
  nums=[2,7,11,15]  
        ^ (j=0)

L3:=================================================================
          v (i=nums.length - 3)
  nums=[2,7,11,15]  
        ^ (j=0)

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
        System.out.println(Arrays.toString(twoSum(new int[]{2, 3, 4}, 6)));
        System.out.println(Arrays.toString(twoSum(new int[]{-1, 0}, -1)));
    }

    public static int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[]{i + 1, j + 1};
            }
            if (sum > target) {
                j--;
            } else {
                i++;
            }
        }
        return new int[0];
    }
}

更加解

上面在LeetCode只贏過14%左右的提交，但看了前面的提交解法都相同，所以應該沒其他更好的解法。