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

#题目描述

给定一个已按 非递减顺序排列 的整数数组 numbers，找出两个数使其相加之和等于目标数 target。

要求：

• 返回这两个数的下标（下标从 1 开始计数）。
• 假设每个输入只对应唯一的答案。
• 不可以重复使用相同的元素。

#思路分析

这道题是经典的两数之和问题的变体，关键区别在于输入数组已排序。这一特性让我们可以使用双指针算法，获得比哈希表更优的空间复杂度。

#为什么可以用双指针？

数组已排序意味着：

• 数组左侧的数较小，右侧的数较大。
• 如果当前两数之和小于目标值，说明需要更大的数，应该将左指针右移。
• 如果当前两数之和大于目标值，说明需要更小的数，应该将右指针左移。
• 通过这种"夹逼"策略，可以在一次遍历中找到答案。

#算法步骤

1. 初始化左指针 left = 0（指向数组起始位置）。
2. 初始化右指针 right = numbers.length - 1（指向数组末尾位置）。
3. 当 left < right 时循环：
   • 计算当前和 sum = numbers[left] + numbers[right]。
   • 如果 sum === target，返回 [left + 1, right + 1]（题目要求下标从 1 开始）。
   • 如果 sum < target，说明和太小，left++（向右移动，选择更大的数）。
   • 如果 sum > target，说明和太大，right--（向左移动，选择更小的数）。
4. 题目保证有唯一解，循环一定能找到答案。

#为什么这个方法不会漏解？

双指针的移动是基于排除法：

• 当 sum < target 时，说明 numbers[left] 与当前 right 及其左侧的所有数相加都小于 target，因此可以安全地排除 numbers[left]，将 left 右移。
• 当 sum > target 时，说明 numbers[right] 与当前 left 及其右侧的所有数相加都大于 target，因此可以安全地排除 numbers[right]，将 right 左移。
• 这样每次移动都排除了一个不可能的候选，最终一定会找到唯一解。

#示例代码

/**
 * 双指针法求两数之和
 * @param numbers 有序数组（升序）
 * @param target 目标和
 * @returns 两个数的索引位置（从 1 开始）
 */
export function twoSum(numbers: number[], target: number): number[] {
    // 左指针从数组起始位置开始
    let left = 0;
    // 右指针从数组末尾位置开始
    let right = numbers.length - 1;

    // 当左指针小于右指针时继续循环
    while (left < right) {
        // 计算当前两个指针指向元素的和
        const sum = numbers[left] + numbers[right];

        // 如果和等于目标值，返回结果（索引需要加 1，因为题目要求从 1 开始）
        if (sum === target) {
            return [left + 1, right + 1]
        }
        // 如果和小于目标值，说明需要更大的数，左指针右移
        else if (sum < target) {
            left++;
        }
        // 如果和大于目标值，说明需要更小的数，右指针左移
        else {
            right--;
        }
    }

    // 没有找到符合条件的两个数，返回空数组
    return [];
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。双指针最多遍历数组一次，每个元素最多被访问一次。
• 空间复杂度：O(1)，只使用了常量级别的额外空间（两个指针变量）。

#示例演示

#示例 1

输入：numbers = [2, 7, 11, 15], target = 9

#示例 2

输入：numbers = [2, 3, 4], target = 6

#示例 3

输入：numbers = [-1, 0], target = -1

#对比：为什么不用哈希表？

经典的两数之和问题（无序数组）通常使用哈希表解决，时间复杂度 O(n)，空间复杂度 O(n)。

而本题由于数组已排序，双指针法可以达到相同的时间复杂度 O(n)，但空间复杂度优化到 O(1)，是更优的选择。