7.相向双指针

相向双指针

解决两数之和，三数之和问题。主要针对有序数组使用。

两数之和

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

三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序
        nums.sort()
        ans=[]
        n=len(nums)
        for i in range(n-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            if nums[i]+nums[i+1]+nums[i+2]>0:
                break
            if nums[i]+nums[-2]+nums[-1]<0:
                continue
            j=i+1
            k=n-1
            while j<k:
                target=nums[i]+nums[j]+nums[k]
                if target>0:
                    k-=1
                elif target<0:
                    j+=1
                else:
                    ans.append([nums[i],nums[j],nums[k]])
                    j+=1
                    while j<k and nums[j]==nums[j-1]:
                        j+=1
                    k-=1
                    while k>j and nums[k]==nums[k+1]:
                        k-=1
        return ans