队列的最大值

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

nums = [2, 7, 11, 15]
target = 9
# 时间复杂度O(n**2)
def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for i in nums:
        for j in nums:
            if target - i == j and i != j:
                return i, j

print(twoSum(nums, target))

因为是递增关系 所以可以采用双指针“多退少补”

#利用递增关系 “多退少补” 时间复杂度O(n) 空间复杂度O(1)
def twoSum2(nums, target):
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s > target:
            j -= 1
        elif s < target:
            i += 1
        else:
            return nums[i], nums[j]
    return []
print(twoSum2(nums, target))