当前位置： 面试刷题>> 三数之和(经典算法150题)
### 题目描述
**三数之和**
给定一个包含n个整数的数组`nums`，以及一个目标值`target`，找出数组中所有三个数的所有独特组合，使得这三个数之和等于`target`。
注意：
- 解答中不能包含重复的三元组。
- 你可以按任意顺序返回答案。
### 示例
**示例 1**:
```
输入: nums = [-1, 0, 1, 2, -1, -4], target = 0
输出: [[-1, 0, 1], [-1, -1, 2]]
```
**示例 2**:
```
输入: nums = [], target = 0
输出: []
```
**示例 3**:
```
输入: nums = [0], target = 0
输出: []
```
### PHP 代码示例
```php
function threeSum($nums, $target) {
$result = [];
sort($nums); // 先对数组进行排序
$length = count($nums);
for ($i = 0; $i < $length - 2; $i++) {
// 跳过重复元素
if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
continue;
}
$left = $i + 1;
$right = $length - 1;
while ($left < $right) {
$sum = $nums[$i] + $nums[$left] + $nums[$right];
if ($sum == $target) {
$result[] = [$nums[$i], $nums[$left], $nums[$right]];
// 跳过重复元素
while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;
while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;
$left++;
$right--;
} elseif ($sum < $target) {
$left++;
} else {
$right--;
}
}
}
return $result;
}
// 示例调用
$nums = [-1, 0, 1, 2, -1, -4];
$target = 0;
$result = threeSum($nums, $target);
print_r($result);
```
### Python 代码示例
```python
def threeSum(nums, target):
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == target:
result.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 s < target:
left += 1
else:
right -= 1
return result
# 示例调用
nums = [-1, 0, 1, 2, -1, -4]
target = 0
result = threeSum(nums, target)
print(result)
```
### JavaScript 代码示例
```javascript
function threeSum(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = n - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
// 跳过重复元素
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
// 示例调用
const nums = [-1, 0, 1, 2, -1, -4];
const target = 0;
const result = threeSum(nums, target);
console.log(result);
```
在以上示例中，我们首先对数组进行排序，然后使用双指针技巧来寻找三数之和等于目标值的组合，并跳过重复元素以避免重复的组合出现在结果中。这种方法的时间复杂度为O(n^2)，空间复杂度主要取决于结果数组的大小，最坏情况下为O(n^2)，但通常会更小。