# LeetCode-3Sum
Date: 2021-05-10


#### **问题:**

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.

Notice that the solution set must not contain duplicate triplets.

 

**Example 1:**

**Input:**

```
 nums = [-1,0,1,2,-1,-4]

```

**Output:**

```
 [[-1,-1,2],[-1,0,1]]

```

**Example 2:**

**Input:**

```
 nums = []

```

**Output:**

```
 []

```

**Example 3:**

**Input:**

```
 nums = [0]

```

**Output:**

```
 []

```

 

**Constraints:**

- `0 <= nums.length <= 3000`
- `-10`5 `<= nums[i] <= 10`5

 

#### **解答:**

与Two Sum不同这个题目中存在相同的数据， 处理思路是先考虑数据不重复， 将list升序排序后，遍历每个元素的同时判断其存在两个值使其满足三数之和为0， 两个值分别取大于当前值的最小值和最大值由于数组是排序的，如果三数之和大于0，那么减小最大值索引， 如果三数之和小于0，增加最小值索引。

- 对于下一个数据和当前数据相同， 跳过

```
if nums[i] == nums[i-1] and i > 0: 
  continue
```

- 2 如果三数之和为0 ， 那么要过滤掉相邻相同的数据

```
while left < right and nums[left] == nums[left +1]: 
  left += 1 
while left < right and nums[right] == nums[right-1]: 
  right -=1
```

 

```
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 1:
            return []
        nums.sort()
        tripleset = []
        pre = 0
        for i in range(len(nums)): 
            if nums[i] == nums[i-1] and i > 0: 
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:            
                sum = nums[i] + nums[left] + nums[right]
                if sum == 0 :
                    tripleset.append([nums[i] ,nums[left], nums[right]])
                    while left < right  and nums[left] == nums[left +1]:
                        left += 1
                    while left < right  and nums[right] == nums[right-1]:
                        right -=1
                    left += 1
                    right -= 1
                elif sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                    
                      
        return tripleset

```

#### **参考及引用**

https://leetcode.com/problems/3sum/discuss/7392/Python-easy-to-understand-solution-(O(n\*n)-time).

Photo by **[Lucas Pezeta](https://www.pexels.com/@lucaspezeta?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)** from **[Pexels](https://www.pexels.com/photo/cityscape-during-nighttime-2294054/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)**