# 3Sum

### 描述​

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, $a \leq b \leq c$)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4}.

A solution set is:

(-1, 0, 1)(-1, -1, 2)

### 代码​

#### 双指针​

# 3Sum# 先排序，然后左右夹逼，注意跳过重复的数# Time Complexity: O(n^2)# Space Complexity: from O(logn) to O(n), depending on the# implementation of the sorting algorithmclass Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        nums.sort()        result = []        for i in range(len(nums)):            if i == 0 or nums[i] != nums[i-1]:                for lst in self.twoSumII(nums, i+1, 0-nums[i]):                    result.append([nums[i]]+lst)        return result    def twoSumII(self, nums: List[int], start: int, target:int)->List[List[int]]:        result = []        low, high = start, len(nums)-1        while low < high:            sum = nums[low] + nums[high];            if sum < target:                low += 1            elif sum > target:                high -= 1            else:                result.append([nums[low], nums[high]])                low += 1                high -= 1                while low < high and nums[low] == nums[low-1]:                    low += 1                while low < high and nums[high] == nums[high+1]:                    high -= 1        return result

#### HashSet​

# 3Sum# 先排序，然后twoSumII()用HashSet实现# Time Complexity: O(n^2), Space Complexity: O(n)class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        nums.sort()        result = []        for i in range(len(nums)):            if i == 0 or nums[i] != nums[i-1]:                for lst in self.twoSumII(nums, i+1, 0-nums[i]):                    result.append([nums[i]]+lst)        return result    def twoSumII(self, nums: List[int], start: int, target:int)->List[List[int]]:        result = []        s = set()        for i in range(start, len(nums)):            if len(result) == 0 or result[-1][1] != nums[i]:                complement = target - nums[i]                if complement in s:                    result.append([complement, nums[i]])            s.add(nums[i])        return result