5. 3Sum （多指针）

题目

评论区思路

首先，超过O(n^2)的方法会超时，所以我们要注意time complexity。 我们先将list排序。下面的方法运用了双指针(mid&right)，left固定作为循环中的第一个数，当第一个数固定之后，原先的3sum就变成了2sum。这种方法和binary sort有点类似，只不过指针是每次移动一个位置。

当然，此题关键点还有result的结果不能重复，也就是说我们要避免重复的答案。而下面代码考虑了会出现的三种情况，每一种情况我都在注释中举了一个例子。

1. left的基点数字与上次一循环一样。我们已知nums已经排序了，以同样数字为基点答案可能会重复且这么做是没有意义的，所以选择跳过。
2. nums[mid] == nums[mid+1]，因为我们之前已经取了[nums[left], nums[mid], nums[right]]，所以要避免[nums[left], nums[mid+1], nums[right]]重复

3. nums[mid] == nums[mid+1]，因为我们之前已经取了[nums[left], nums[mid], nums[right]]，所以要避免[nums[left], nums[mid], nums[right-1]]重复

   class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for left in range(len(nums)-2):
            # escape case like [-1, -1, -1, 2], so that we only count [-1,-1,2] once
            if left>0 and nums[left] == nums[left-1]:
                continue
            mid = left + 1
            right = len(nums) - 1
            while mid < right:
                total = nums[left] + nums[mid] + nums[right]
                if total < 0:
                    mid += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[left], nums[mid], nums[right]])
                    # case like [-2,-1,-1,-1,2] such that [-1,-1,2] only count once
                    while mid < right and nums[mid] == nums[mid+1]:
                        mid += 1
                    # case like [-2,1,1,1,1] such that [-2,1,1] only count once
                    while mid < right and nums[right] == nums[right-1]:
                        right -= 1
                    mid += 1
                    right -= 1
        return result