leetcode 167. Two Sum II - Input Array Is Sorted 兩數之和 II - 輸入有序數組

一、題目大意

https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

給你一個下标從 1 開始的整數數組 numbers ，該數組已按 非遞減順序排列  ，請你從數組中找出滿足相加之和等于目标數 target 的兩個數。如果設這兩個數分别是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數數組 [index1, index2] 的形式傳回這兩個整數的下标 index1 和 index2。

你可以假設每個輸入 隻對應唯一的答案 ，而且你 不可以 重複使用相同的元素。

你所設計的解決方案必須隻使用常量級的額外空間。

示例 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] 。

** 提示：**

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非遞減順序 排列
• -1000 <= target <= 1000
• 僅存在一個有效答案

二、解題思路

用雙指向反向周遊來解決，因為是已排序數組。

三、解題方法

3.1 Java實作

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

四、總結小記

• 2022/5/16 一道題做熟了就簡單了