双指针算法

元素：数组
目标：求三数之和
思路：数组遍历

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]

• 计算三个数的和 sum 判断是否满足为 0 ，满足则添加进结果集
  如果 i=0时nums[i] 大于 0，则三数之和必然无法等于 0，结束循环
  如果 nums[i] = nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
  当 sum = 0 时，nums[L] = nums[L-1] 则会导致结果重复，应该跳过，L++
  当 sum = 0 时，nums[R] = nums[R+1] 则会导致结果重复，应该跳过，R--
  时间复杂度：O(n^2) n 为数组长度

上代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        lenums = len(nums)
        for i in range(lenums-2):
            if i==0 and nums[i]>0:
                break
            if i>0 and nums[i]==nums[i-1]:
                continue
            left = i+1
            right = lenums - 1
            while left < right:
                sums = nums[i]+nums[left]+nums[right]
                if sums < 0:
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                elif sums > 0:
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                else:
                    res.append([nums[i],nums[left],nums[right]])
                    left +=1
                    right -=1
                    while left < right and nums[left]==nums[left-1]:
                        left +=1
                    while left < right and nums[right]==nums[right+1]:
                        right -=1
        return res

1572512598(1).png