【LeetCode.167】 两数之和 II - 输入有序数组

题目描述

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例：

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

理解题意

• 注意返回下标是索引+1，而不是原索引。
• 只有唯一的答案。作为答案的两个元素，如果是相等的，那么肯定有两个这个元素。
• 相比原题，多了有序数组的条件，必须利用。

解法——双端指针

解法关键词：

• 双指针
• 双端指针

双端指针如果是用来遍历单个元素时，肯定没有问题的，最终每个元素都能遍历到。但此题实际是，要求我们去遍历元素的组合，即两个元素的组合，那么双端指针在遍历过程中，肯定不能遍历到所有组合情况，或者说，在遍历过程中，它会选择方向，适当排除掉某些情况。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers)-1

        while(left < right):
            theSum = numbers[left]+numbers[right]
            if theSum == target:
                return [left+1,right+1]  #返回下标是索引+1
            elif theSum < target:
                left += 1
            elif theSum > target:
                right -= 1

• 首先，确实是个挺标准的双端指针。一种情况移动左指针，另一种情况移动右指针。
• 观察left right的初始情况，可见搜索范围在[left, right]的搜索空间内。
• 由于是两个元素的组合，最终结果不可能出现left == right的情况，所以循环条件为left < right。
• 重要的是，去理解左右指针移动的前提条件：
  • 当theSum < target时，说明两数之和应该更大。此时，right元素可能已经找到了，只是left元素还需往右移动。所以，此时必须移动left，不然可能就此错过答案。
  • 同理，当theSum > target时，说明两数之和应该更小。此时移动right。

题型变异

修改条件：可以重复使用相同的元素。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers)-1

        while(left <= right):  #答案可能是left与right相等，所以只需修改此处
            theSum = numbers[left]+numbers[right]
            if theSum == target:
                return [left+1,right+1] 
            elif theSum < target:
                left += 1
            elif theSum > target:
                right -= 1