167.两数之和 II - 输入有序数组(Easy)

题目描述

LeetCode 两道相似的题目：面试题57. 和为s的两个数字 - II 、167. 两数之和 II - 输入有序数组

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

样例

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

解题思路

滑动窗口

参考资料： 什么是滑动窗口，以及如何用滑动窗口解这道题（C++/Java/Python）

• 数据段的和小于target：右端右移
• 数据段的和大于target：左端右移
• 数据段的和等于target: 加入结果，并且左端右移

代码

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

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            if numbers[l] + numbers[r] == target:
                return [l + 1, r + 1]
            elif numbers[l] + numbers[r] < target:
                l += 1
            else:
                r -= 1
        return 

面试题57. 和为s的两个数字 - II

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l, r = 1, 1
        s = 1 # 默认先将 1 加入
        ans = []
        while r < target:  # target 一定取不到，因为要求至少包含两个数
            if s < target:  # 右指针右移
                r += 1
                s += r 
            elif s > target:  # 左指针右移
                s -= l
                l += 1
            else:
                ans.append(list(range(l, r + 1))) # 加入
                s -= l  # 加入结果后继续做左指针右移
                l += 1
        return ans