双指针算法

思考过程：暴力o(n^2)->单调性->优化

只用一个while

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        l, r = 0, n - 1
        sum = 0 # 记录两指针对应总和
        while l < r:
            sum = numbers[l] + numbers[r]
            if sum == target:
                return [l+1, r+1]
            # 总和小则左指针右移，否则右指针左移
            elif sum < target:
                l += 1
            else:
                r -= 1

参考yxc

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = len(nums) - 1
        j = 0
        while j < len(nums):
            # 当右指针左移后仍在左指针右边且移完后两个指针之和大于等于target，则右指针左移
            while i - 1 > j and nums[i - 1] + nums[j] >= target: i -= 1
            if nums[i] + nums[j] == target: 
                return [j + 1, i + 1] # 索引加一是因为返回下标从1开始           
            j +=1 # 若右指针不能左移，说明总和小于目标值，则左指针右移
        return None