# 18. 4Sum - LeetCode Best Practices

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

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

## LeetCode description of "18. 4Sum"

Given an array `nums` of `n` integers, return *an array of all the* ***unique*** *quadruplets* `[nums[a], nums[b], nums[c], nums[d]]` such that:

- `0 <= a, b, c, d < n`
- `a`, `b`, `c`, and `d` are **distinct**.
- `nums[a] + nums[b] + nums[c] + nums[d] == target`
- You may return the answer in **any order**.

### [Example 1]

**Input**: `nums = [1,0,-1,0,-2,2], target = 0`

**Output**: `[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`

### [Example 2]

**Input**: `nums = [2,2,2,2,2], target = 8`

**Output**: `[[2,2,2,2]]`

### [Constraints]

- `1 <= nums.length <= 200`
- `-10^9 <= nums[i] <= 10^9`
- `-10^9 <= target <= 10^9`

## Intuition

1. The idea of this question is the same as [15. 3Sum](15-3sum.md), please click the link to view.
2. The difference is that `three numbers` becomes `four numbers`, and processing `four numbers` only requires **one more nested loop**.
3. In addition, the `target` parameter is added, which needs to be brought in as a condition during calculation.
4. You may have already seen that no matter it is `two numbers`, `three numbers` or `four numbers`, the `Two Pointers Technique` can be used.

## Complexity

- Time complexity: `O(N^3)`.
- Space complexity: `O(N)`.

## Python

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

        for i in range(len(nums) - 3):
            for j in range(i + 1, len(nums) - 2):
                num = nums[i] + nums[j]
                # if num > target / 2:
                #     break
                left = j + 1
                right = len(nums) - 1

                while left < right:
                    sum_ = nums[left] + nums[right]

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

## JavaScript

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

  // Uncomment to speed up
  // let nums2 = [];
  // for (let i = 0; i < nums.length; i++) {
  //   if (i >= 4 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3] && nums[i-3] === nums[i-4]) {
  //     continue;
  //   }
  //   nums2.push(nums[i]);
  // }
  // nums = nums2;
  
  const results = new Set();
  
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      const num = nums[i] + nums[j];
      // Uncomment to speed up
      // if (num > target / 2) {
      //   break;
      // }
      let left = j + 1;
      let right = nums.length - 1;
      
      while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target - num) {
          results.add([nums[i], nums[j], nums[left], nums[right]].join(','));
          left++;
        } else if (sum > target - num) {
          right--;
        } else {
          left++;
        }
      }
    }
  }
  
  return Array.from(results).map(str => str.split(',').map(Number));
};
```

## Ruby

```ruby
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
  nums.sort!

  # Uncomment to speed up
  # nums2 = []
  # nums.each_with_index do |num, i|
  #   next if i >= 4 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]
  #   nums2 << num
  # end
  # nums = nums2
  
  results = Set.new
  
  (0..nums.length-4).each do |i|
    (i+1..nums.length-3).each do |j|
      num = nums[i] + nums[j]
      # Uncomment to speed up
      # break if num > target / 2
      left = j + 1
      right = nums.length - 1
      
      while left < right
        sum = nums[left] + nums[right]
        
        if sum == target - num
          results.add([nums[i], nums[j], nums[left], nums[right]])
          left += 1
        elsif sum > target - num
          right -= 1
        else
          left += 1
        end
      end
    end
  end
  
  results.to_a
end
```

## Java

```java
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<>();
        
        Arrays.sort(nums);
        Set<List<Integer>> seen = new HashSet<>();
        
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int left = j + 1;
                int right = nums.length - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        List<Integer> quadruplet = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        if (!seen.contains(quadruplet)) {
                            results.add(quadruplet);
                            seen.add(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return results;
    }
}
```

## C++

```cpp
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> results;
        
        sort(nums.begin(), nums.end());
        set<vector<int>> seen;
        
        for (int i = 0; i < nums.size() - 3; i++) {
            for (int j = i + 1; j < nums.size() - 2; j++) {
                int left = j + 1;
                int right = nums.size() - 1;
                
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        vector<int> quadruplet = {nums[i], nums[j], nums[left], nums[right]};
                        if (seen.find(quadruplet) == seen.end()) {
                            results.push_back(quadruplet);
                            seen.insert(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return results;
    }
};
```

## Go

```go
// If you want the program to run faster, uncomment the two places in the code.

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)

    // nums2 := make([]int, 0)
    // for i := 0; i < len(nums); i++ {
    //     if i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4] {
    //         continue
    //     }
    //     nums2 = append(nums2, nums[i])
    // }
    // nums = nums2
    
    results := make([][]int, 0)
    seen := make(map[string]bool)
    
    for i := 0; i < len(nums)-3; i++ {
        for j := i + 1; j < len(nums)-2; j++ {
            num := nums[i] + nums[j]
            // if num > target/2 {
            //     break
            // }
            left := j + 1
            right := len(nums) - 1
            
            for left < right {
                sum := nums[left] + nums[right]
                
                if sum == target-num {
                    quadruplet := []int{nums[i], nums[j], nums[left], nums[right]}
                    key := fmt.Sprintf("%d,%d,%d,%d", quadruplet[0], quadruplet[1], quadruplet[2], quadruplet[3])
                    if !seen[key] {
                        results = append(results, quadruplet)
                        seen[key] = true
                    }
                    left++
                } else if sum > target-num {
                    right--
                } else {
                    left++
                }
            }
        }
    }
    
    return results
}
```

## C#

```csharp
// If you want the program to run faster, uncomment the two places in the code.
public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);

        // List<int> nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]) {
        //         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 - 3; i++) {
            for (int j = i + 1; j < nums.Length - 2; j++) {
                long num = (long)nums[i] + nums[j];
                // if (num > target / 2) {
                //     break;
                // }
                int left = j + 1;
                int right = nums.Length - 1;
                
                while (left < right) {
                    long sum = (long)nums[left] + nums[right];
                    
                    if (sum == target - num) {
                        var quadruplet = new[] { nums[i], nums[j], nums[left], nums[right] };
                        string key = string.Join(",", quadruplet);
                        if (!seen.Contains(key)) {
                            results.Add(quadruplet);
                            seen.Add(key);
                        }
                        left++;
                    } else if (sum > target - num) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        
        return results;
    }
}
```

## 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: [18. 4Sum - LeetCode Best Practices](https://leetcoder.net/en/leetcode/18-4sum).

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