两数之和 II - 输入有序数组

🟡 Medium · 🏷️ 数组、双指针、二分查找 · LeetCode#167

📖 题目

在有序数组里找两个数，使它们的和等于 target，返回下标（从 1 开始）。

输入	输出	说明
numbers=[2,7,11,15], target=9	[1,2]	2+7=9

💡 思路

跟两数之和是同一个问题，区别是数组有序——哈希表的做法仍然可行，但排序这个条件没被用上，白白浪费了 O(n) 的额外空间。

有序数组适合用对撞双指针：左指针从头、右指针从尾，往中间靠拢。两数之和比 target 小，说明需要更大的数，左指针右移；比 target 大，右指针左移。

这是双指针的第三种玩法：移动零是快慢指针（同向），合并两个有序数组是逆向双指针（从后往前），这题是对撞双指针（两端往中间）。

💻 代码

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]   # 下标从 1 开始
            elif s < target:
                left += 1
            else:
                right -= 1

时间复杂度 O(n)，空间复杂度 O(1)——跟哈希表解法时间一样，但省掉了额外空间，这正是"有序"这个条件被用上的地方。