# 15. 3Sum - LeetCode Best Practices

Visit original link: [15. 3Sum - LeetCode Best Practices](https://leetcoder.net/en/leetcode/15-3sum) for a better experience!

LeetCode link: [15. 3Sum](https://leetcode.com/problems/3sum), difficulty: **Medium**.

## LeetCode description of "15. 3Sum"

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]]`

**Explanation**: 

<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>
The distinct triplets are [-1,0,1] and [-1,-1,2].<br>
Notice that the order of the output and the order of the triplets does not matter.</p>


### [Example 2]

**Input**: `nums = [0,1,1]`

**Output**: `[]`

**Explanation**: 

<p>The only possible triplet does not sum up to 0.</p>


### [Example 3]

**Input**: `nums = [0,0,0]`

**Output**: `[[0,0,0]]`

**Explanation**: `The only possible triplet sums up to 0.`

### [Constraints]

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

### [Hints]

<details>
  <summary>Hint 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>Hint 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>Hint 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>

## Intuition 1

1. The `sum` of three numbers equals `0`, which is equivalent to the `sum` of *two numbers* equaling the ***negative*** third number.
2. There are two options:
    - Option 1. First `determine one number`, and then `find the other two numbers`.
    - Option 2. First `determine two numbers`, and then `find the third number`.
3. If you choose `option 2`, you need to use `Map`. Because you need to deduplicate `nums`; when searching for the third number in `Map`, you also need to avoid the two numbers that have been determined, which is more troublesome to implement.
4. If you choose `option 1`, you need to use the `two pointers` algorithm when searching for the other two numbers.
5. For `option 2`, only the `Python` sample code is given. This article focuses on `option 1`.

## Steps

1. Sort `nums`.
2. Iterate over `nums`.
3. pseudocode:

    ```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
          }
       }
    }
    ```

## Complexity

- Time complexity: `O(N * N)`.
- Space complexity: `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!
```

## Intuition 2

Please refer to the idea of `​​​​Solution 1`. Here we only give the code to explain why using `Map` is not a good idea.

## Complexity

- Time complexity: `O(N * N)`.
- Space complexity: `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!
```

Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website [leetcoder.net](https://leetcoder.net): Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!

Original link: [15. 3Sum - LeetCode Best Practices](https://leetcoder.net/en/leetcode/15-3sum).

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