LeetCode中如何解决两数之和输入有序数组的问题

# LeetCode中如何解决两数之和输入有序数组的问题

## 问题描述

在LeetCode的"两数之和 II - 输入有序数组"（Two Sum II - Input Array Is Sorted）问题中，给定一个已按**非递减顺序排列**的整数数组`numbers`和一个目标值`target`，我们需要找到两个不同的索引`index1`和`index2`（其中`1 ≤ index1 < index2 ≤ numbers.length`），使得这两个索引对应的数字之和等于`target`。

题目保证**仅存在一个有效解**，且要求返回的索引不是从零开始，而是从1开始计数。

**示例：**

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 + 7 = 9

## 解题思路

### 方法一：双指针法（最优解）

由于数组是有序的，我们可以利用这一特性，通过**双指针**技术高效地解决问题：

1. **初始化指针**：
   - 左指针`left`指向数组起始位置（`index = 0`）
   - 右指针`right`指向数组末尾（`index = numbers.length - 1`）

2. **循环移动指针**：
   - 计算当前两数之和`sum = numbers[left] + numbers[right]`
   - 如果`sum == target`，直接返回`[left + 1, right + 1]`（题目要求索引从1开始）
   - 如果`sum < target`，说明需要更大的数，因此左指针右移（`left++`）
   - 如果`sum > target`，说明需要更小的数，因此右指针左移（`right--`）

3. **终止条件**：当`left >= right`时终止循环（题目保证有解，无需额外判断）

**时间复杂度**：O(n)，仅需一次遍历。  
**空间复杂度**：O(1)，仅使用常数空间。

```python
def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]  # 题目保证有解，此行实际不会执行

方法二：二分查找（适用于更大规模数据）

如果数组非常大，双指针法的线性时间可能不够高效。此时可以结合二分查找优化：

1. 固定一个数：遍历数组，假设当前数为numbers[i]。
2. 二分查找另一个数：在剩余数组中（i+1到末尾）查找target - numbers[i]。

时间复杂度：O(n log n)，每次二分查找耗时O(log n)。
空间复杂度：O(1)。

def twoSum(numbers: List[int], target: int) -> List[int]:
    for i in range(len(numbers)):
        left, right = i + 1, len(numbers) - 1
        complement = target - numbers[i]
        while left <= right:
            mid = (left + right) // 2
            if numbers[mid] == complement:
                return [i + 1, mid + 1]
            elif numbers[mid] < complement:
                left = mid + 1
            else:
                right = mid - 1
    return [-1, -1]

方法三：哈希表（通用解法，但未利用有序特性）

虽然题目中数组有序，但哈希表法仍然适用（与经典两数之和解法相同）：

1. 维护一个哈希表：记录已遍历过的数字及其索引。
2. 遍历数组：对于每个数numbers[i]，检查target - numbers[i]是否在哈希表中。

时间复杂度：O(n)。
空间复杂度：O(n)，需要额外存储哈希表。

def twoSum(numbers: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(numbers):
        complement = target - num
        if complement in seen:
            return [seen[complement] + 1, i + 1]
        seen[num] = i
    return [-1, -1]

方法对比与选择

推荐选择双指针法，因为它完美利用了有序特性，且时间和空间复杂度最优。

边界条件与测试案例

1. 最小输入：

   
   numbers = [1, 2], target = 3 → 输出 [1, 2]
   

2. 无解情况（题目已保证有解，但实际代码需处理）：

   
   numbers = [1, 2], target = 5 → 输出 [-1, -1]
   

3. 重复元素：

   
   numbers = [1, 1, 3], target = 2 → 输出 [1, 2]
   

总结

通过双指针法，我们能够高效解决有序数组的两数之和问题。其核心思想是利用有序特性，通过指针移动逐步逼近目标值，避免了不必要的计算。在实际面试中，面试官可能会进一步要求证明其正确性或讨论其他变种问题（如三数之和），因此理解算法本质至关重要。

关键点：
- 双指针法的移动逻辑（何时左移/右移）。
- 有序数组的特性如何降低时间复杂度。
- 索引从1开始的细节处理。 “`