'''
剑指offer 57 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
'''
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 双指针
        left = 0
        right = len(nums)-1
        result = []
        if nums is None or len(nums)==0: return result
        while left < right:
            total = nums[left]+nums[right]
            if total < target:   # 右指针代表list中的最大值，left+最大值都小于target，说明nums[left]需要变得更大
                left += 1
            elif total > target:   # 左指针代表list中最小值，最小值+right大于target，说明nums[right]需要变小
                right -= 1
            else: # target == total
                result.append(nums[left])
                result.append(nums[right])
                return result
