📃 题目描述

题目链接：

• 剑指 Offer II 006. 排序数组中两个数字之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

🔔 解题思路

不同于 1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 这道用哈希表做的题目（当然你按照哈希表的做法去做也没问题），本题要求第一个数一定要在第二个数的左边，并且，更重要的是，数组已经是有序的！（有序且包含重复元素，各位可能马上就想到了可以用二分查找，固定一个数，二分查找另一个数，显然这样效率不是很高）

我们使用两个指针，一个指向数组开头，一个指向数组结尾：

• 若两个指针指向的数之和 < target，left 右移；
• 若两个指针指向的数之和 > target，right 左移；

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0 || numbers[0] > target) {
            return new int[0];
        }

        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left, right};
            }
            else if (sum < target) {
                left ++;
            }
            else {
                right --;
            }
        }

        return new int[0];
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)