# 15. 三数之和 - 力扣题解最佳实践

访问原文链接：[15. 三数之和 - 力扣题解最佳实践](https://leetcoder.net/zh/leetcode/15-3sum)，体验更佳！

力扣链接：[15. 三数之和](https://leetcode.cn/problems/3sum), 难度：**中等**。

## 力扣“15. 三数之和”问题描述

给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 `0` 且不重复的三元组。

**注意**：答案中**不**可以包含**重复**的三元组。


### [示例 1]

**输入**: `nums = [-1,0,1,2,-1,-4]`

**输出**: `[[-1,-1,2],[-1,0,1]]`

**解释**: 

<p>nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。<br>
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。<br>
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。<br>
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。<br>
注意，输出的顺序和三元组的顺序并不重要。</p>


### [示例 2]

**输入**: `nums = [0,1,1]`

**输出**: `[]`

**解释**: `唯一可能的三元组和不为 0 。`

### [示例 3]

**输入**: `nums = [0,0,0]`

**输出**: `[[0,0,0]]`

**解释**: `唯一可能的三元组和为 0 。`

### [约束]

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

### [Hints]

<details>
  <summary>提示 1</summary>
  So, we essentially need to find three numbers `x`, `y`, and `z` such that they add up to the given value. If we fix one of the numbers say `x`, we are left with the two-sum problem at hand!

  
</details>

<details>
  <summary>提示 2</summary>
  For the two-sum problem, if we fix one of the numbers, say `x`, we have to scan the entire array to find the next number `y`, which is `value - x` where value is the input parameter. Can we change our array somehow so that this search becomes faster?

  
</details>

<details>
  <summary>提示 3</summary>
  The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

  
</details>

## 思路 1

1. 三个数相加等于0，等同于`两个数相加的和`等于`负的第三个数`。
2. 有两种方案可供选择：
    1. 先定下一个数，然后查找另外两个数。
    2. 先定下两个数，然后查找第三个数。
3. 如果选择`方案2`，需要用到`Map`。因为需要对`nums`去重复；在`Map`中查找`第三个数`时，还需要避开已经定下的`两个数`，实现起来会比较麻烦。
4. 如果选择`方案1`，查找另外两个数时，需要用到`双指针`算法。
5. 对于`方案2`，仅给出了`Python`示例代码。下文重点讲`方案1`。

## 步骤

1. 对`nums`进行排序。
2. 遍历`nums`。
3. 伪代码：

    ```javascript
    for (i = 0; i < nums.length; i++) {
       left = i + 1
       right = nums.length - 1

       while (left < right) {
          if (condition1) {
             left += 1
          } else (condition2) {
             right -= 1
          }
       }
    }
    ```

## 复杂度

- 时间复杂度: `O(N * N)`.
- 空间复杂度: `O(N)`.

## Python

```python
# If you want the program to run faster, uncomment the two places in the code. 
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 3 and num == nums[i - 1] == nums[i - 2] == nums[i - 3]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i, num in enumerate(nums[:len(nums) - 2]):
            # if num > 0:
            #     break
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum_ = nums[left] + nums[right]
                if sum_ == -num:
                    results.add((num, nums[left], nums[right]))
                    left += 1
                elif sum_ > -num:
                    right -= 1
                else:
                    left += 1
        
        return list(results)
```

## Ruby

```ruby
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
  nums.sort!
  results = Set.new

  nums_2 = []
  nums.each_with_index do |num, i|
    next if i >= 3 && num == nums[i - 1] && num == nums[i - 2] && num == nums[i - 3]
    nums_2.append(num)
  end

  nums = nums_2

  # Iterate through each number as potential first element
  (0...nums.length - 2).each do |i|
    break if nums[i] > 0

    left = i + 1
    right = nums.length - 1

    # Two-pointer approach for remaining elements
    while left < right
      current_sum = nums[i] + nums[left] + nums[right]
      if current_sum == 0
        # Add sorted triplet to avoid duplicates
        results.add([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1
      elsif current_sum < 0
        left += 1 # Need larger sum
      else
        right -= 1 # Need smaller sum
      end
    end
  end

  results.to_a
end
```

## Go

```go
func threeSum(nums []int) [][]int {
    sort.Ints(nums)

    nums2 := make([]int, 0)
    for i, num := range nums {
        if i >= 3 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] {
            continue
        }
        nums2 = append(nums2, num)
    }

    nums = nums2
    results := make([][]int, 0)
    seen := make(map[string]bool)

    for i := 0; i < len(nums)-2; i++ {
        // if nums[i] > 0 {
        //     break
        // }

        left := i + 1
        right := len(nums) - 1

        for left < right {
            sum := nums[left] + nums[right]
            if sum == -nums[i] {
                triplet := []int{nums[i], nums[left], nums[right]}
                key := fmt.Sprintf("%d,%d,%d", triplet[0], triplet[1], triplet[2])
                if !seen[key] {
                    results = append(results, triplet)
                    seen[key] = true
                }
                left++
            } else if sum > -nums[i] {
                right--
            } else {
                left++
            }
        }
    }

    return results
}
```

## C++

```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        // Uncomment to speed up
        // vector<int> nums2;
        // for (int i = 0; i < nums.size(); i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] &&
        //     nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.push_back(nums[i]);
        // }
        // nums = nums2;

        vector<vector<int>> results;
        set<vector<int>> seen;

        for (int i = 0; i < nums.size() - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == -nums[i]) {
                    vector<int> triplet = {nums[i], nums[left], nums[right]};

                    if (seen.find(triplet) == seen.end()) {
                        results.push_back(triplet);
                        seen.insert(triplet);
                    }

                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
};
```

## JavaScript

```javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);

    // Uncomment to speed up
    // let nums2 = [];
    // for (let i = 0; i < nums.length; i++) {
    //     if (i >= 3 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3]) {
    //         continue;
    //     }
    //     nums2.push(nums[i]);
    // }
    // nums = nums2;
    
    const results = [];
    const seen = new Set();
    
    for (let i = 0; i < nums.length - 2; i++) {
        // Uncomment to speed up
        // if (nums[i] > 0) {
        //     break;
        // }
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            const sum = nums[left] + nums[right];

            if (sum === -nums[i]) {
                const triplet = [nums[i], nums[left], nums[right]];
                const key = triplet.join(',');
                if (!seen.has(key)) {
                    results.push(triplet);
                    seen.add(key);
                }
                left++;
            } else if (sum > -nums[i]) {
                right--;
            } else {
                left++;
            }
        }
    }
    
    return results;
};
```

## C#

```csharp
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);

        // Uncomment to speed up
        // var nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();
        
        var results = new List<IList<int>>();
        var seen = new HashSet<string>();
        
        for (int i = 0; i < nums.Length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.Length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    var triplet = new List<int> { nums[i], nums[left], nums[right] };
                    string key = string.Join(",", triplet);
                    if (!seen.Contains(key)) {
                        results.Add(triplet);
                        seen.Add(key);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return results;
    }
}
```

## Java

```java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        // Uncomment to speed up
        // List<Integer> nums2 = new ArrayList<>();
        // for (int i = 0; i < nums.length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.add(nums[i]);
        // }
        // nums = nums2.stream().mapToInt(i -> i).toArray();
        
        List<List<Integer>> results = new ArrayList<>();
        var seen = new HashSet<>();
        
        for (int i = 0; i < nums.length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[left], nums[right]);
                    if (!seen.contains(triplet)) {
                        results.add(triplet);
                        seen.add(triplet);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return results;
    }
}
```

## Other languages

```java
// Welcome to create a PR to complete the code of this language, thanks!
```

## 思路 2

请参考`题解1`的思路，本处仅给出代码，用来解释为什么使用 `Map` 不是一个好办法。

## 复杂度

- 时间复杂度: `O(N * N)`.
- 空间复杂度: `O(N)`.

## Python

```python
# from collections import defaultdict

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = duplicate_removed_nums(nums)

        results = set()
        num_to_indices = defaultdict(list)

        for i, num in enumerate(nums):
            num_to_indices[num].append(i)

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if -(nums[i] + nums[j]) in num_to_indices:
                    for index in num_to_indices[-(nums[i] + nums[j])]:
                        if index not in (i, j):
                            result = [nums[i], nums[j], nums[index]]
                            result.sort()
                            results.add(tuple(result))

        return list(results)


def duplicate_removed_nums(nums):
    num_to_count = defaultdict(int)

    for i, num in enumerate(nums):
        if num_to_count[num] <= 2 or (num_to_count[num] <= 3 and num == 0):
            num_to_count[num] += 1

    new_nums = []

    for num in num_to_count:
        new_nums.extend([num] * num_to_count[num])
    
    return new_nums
```

## Other languages

```java
// Welcome to create a PR to complete the code of this language, thanks!
```

亲爱的力扣人，为了您更好的刷题体验，请访问 [leetcoder.net](https://leetcoder.net/zh)。
本站敢称力扣题解最佳实践，终将省你大量刷题时间！

原文链接：[15. 三数之和 - 力扣题解最佳实践](https://leetcoder.net/zh/leetcode/15-3sum).

GitHub 仓库: [f*ck-leetcode](https://github.com/fuck-leetcode/fuck-leetcode).