LeetCode 167. Two Sum II - Input Array Is Sorted 题解

LeetCode 167. 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] 。

解题思路

方法：双指针

思路：

• 使用两个指针left和right，分别指向数组的起始位置和结束位置
• 计算sum = numbers[left] + numbers[right]
• 如果sum == target，返回[left+1, right+1]（因为下标从 1 开始）
• 如果sum < target，移动left指针向右
• 如果sum > target，移动right指针向左
• 直到找到答案

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历数组一次。
• 空间复杂度：O(1)，只需要常数级的额外空间。

代码实现

方法：双指针

class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: # 初始化双指针 left = 0 right = len(numbers) - 1 # 双指针遍历 while left < right: sum_val = numbers[left] + numbers[right] if sum_val == target: # 返回下标（从 1 开始） return [left + 1, right + 1] elif sum_val < target: # 移动左指针向右 left += 1 else: # 移动右指针向左 right -= 1 # 如果没有找到答案，返回空列表 return []

测试用例

测试用例 1：

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

测试用例 2：

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

测试用例 3：

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

总结

本题是双指针的经典应用问题，主要考察对双指针技巧的理解和使用。通过使用双指针，我们可以高效地在有序数组中找到两个数，使得它们的和等于目标值。

双指针的核心思想是：使用两个指针分别指向数组的起始位置和结束位置，根据它们的和与目标值的关系移动指针，直到找到答案。

这种方法不仅适用于两数之和 II 问题，还可以应用于许多其他需要在有序数组中寻找元素的问题。掌握双指针的使用，对于解决这类问题非常重要。