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返回[left1, right1]因为下标从 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 问题还可以应用于许多其他需要在有序数组中寻找元素的问题。掌握双指针的使用对于解决这类问题非常重要。