15. 3Sum

 1class Solution:
 2    def threeSum(self, nums: List[int]) -> List[List[int]]:
 3        nums.sort()
 4        n = len(nums)
 5        result = []
 6
 7        for i in range(n):
 8            # skip duplicates
 9            if i > 0 and nums[i] == nums[i - 1]:
10                continue
11
12            target = -nums[i]
13            l, r = i + 1, n - 1
14            while l < r:
15                if nums[l] + nums[r] == target:
16                    result.append([nums[i], nums[l], nums[r]])
17                    l += 1
18                    r -= 1
19                    while l < r and nums[l] == nums[l - 1]:
20                        l += 1
21                    while l < r and nums[r] == nums[r + 1]:
22                        r -= 1
23                elif nums[l] + nums[r] < target:
24                    l += 1
25                else:
26                    r -= 1
27
28        return result