# 18. 四数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解
访问原文链接：[18. 四数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解](https://leetcode.to/zh/leetcode/18-4sum)，体验更佳！
力扣链接：[18. 四数之和](https://leetcode.cn/problems/4sum), 难度等级：**中等**。
## LeetCode “18. 四数之和”问题描述
给你一个由 `n` 个整数组成的数组 `nums` ，和一个目标值 `target` 。请你找出并返回满足下述全部条件且**不重复**的四元组 `[nums[a], nums[b], nums[c], nums[d]]` （若两个四元组元素一一对应，则认为两个四元组重复）：
- `0 <= a, b, c, d < n`
- `a`、`b`、`c` 和 `d` **互不相同**
- `nums[a] + nums[b] + nums[c] + nums[d] == target`
你可以按 **任意顺序** 返回答案 。
### [示例 1]
**输入**: `nums = [1,0,-1,0,-2,2], target = 0`
**输出**: `[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`
### [示例 2]
**输入**: `nums = [2,2,2,2,2], target = 8`
**输出**: `[[2,2,2,2]]`
### [约束]
- `1 <= nums.length <= 200`
- `-10^9 <= nums[i] <= 10^9`
- `-10^9 <= target <= 10^9`
## 思路
1. 本题思路同[15. 三数之和](15-3sum.md), 请点链接查看。
2. 区别是`三数`变`四数`，处理`四数`，只需要**多加一重嵌套的循环**。
3. 另外增加了`target`参数，计算时需要把它做为条件带入。
4. 你可能已经看出来了，不管它是`两数`、`三数`还是`四数`，都可以用`双指针技术`。
## 复杂度
- 时间复杂度: `O(N^3)`.
- 空间复杂度: `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> fourSum(int[] nums, int target) {
List> results = new ArrayList<>();
Arrays.sort(nums);
Set> 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 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> fourSum(vector& nums, int target) {
vector> results;
sort(nums.begin(), nums.end());
set> 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 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> FourSum(int[] nums, int target) {
Array.Sort(nums);
// List nums2 = new List();
// 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>();
var seen = new HashSet();
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!
```
亲爱的力扣人，为了您更好的刷题体验，请访问 [LeetCode.to](https://leetcode.to/zh)。
本站敢称力扣题解最佳实践，终将省你大量刷题时间！
原文链接：[18. 四数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解](https://leetcode.to/zh/leetcode/18-4sum).
GitHub 仓库: [leetcode-python-java](https://github.com/leetcode-python-java/leetcode-python-java).