# LeetCode 15. 三数之和 - C++ 实现
## 解题思路：排序 + 双指针
```
1. 对数组排序
2. 固定第一个数 nums[i]，双指针在 [i+1, n-1] 中找两数之和 = -nums[i]
3. 三处去重，避免重复三元组
```
**时间复杂度**: O(n²)
**空间复杂度**: O(log n)（排序栈空间）
---
## C++ 实现
```cpp
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
if (n < 3) return result;
sort(nums.begin(), nums.end()); // 排序
for (int i = 0; i < n - 2; i++) {
// ① 去重：跳过重复的第一个数
if (i > 0 && nums[i] == nums[i - 1])
continue;
// ② 剪枝：最小值 > 0，后面不可能有解
if (nums[i] > 0)
break;
int left = i + 1;
int right = n - 1;
int target = -nums[i]; // 需要找的两数之和
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.push_back({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;
}
};
```
---
## 测试代码
```cpp
#include <iostream>
int main() {
Solution sol;
// 测试用例 1
vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> res1 = sol.threeSum(nums1);
cout << "Test 1: ";
for (auto& v : res1) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: [-1, -1, 2] [-1, 0, 1]
cout << endl;
// 测试用例 2
vector<int> nums2 = {0, 1, 1};
vector<vector<int>> res2 = sol.threeSum(nums2);
cout << "Test 2: ";
for (auto& v : res2) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: (空)
cout << endl;
// 测试用例 3
vector<int> nums3 = {0, 0, 0};
vector<vector<int>> res3 = sol.threeSum(nums3);
cout << "Test 3: ";
for (auto& v : res3) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: [0, 0, 0]
return 0;
}
```
---
## 关键要点总结
| 要点 | 说明 |
|------|------|
| 排序 | `sort(nums.begin(), nums.end())` |
| 剪枝 | `nums[i] > 0` 时直接 break，因为后面全是正数 |
| 去重① | `i > 0 && nums[i] == nums[i-1]` 跳过重复第一个数 |
| 去重②③ | 找到解后，left/right 跳过相同值再移动 |
| 边界 | `n < 3` 直接返回空 |
---
## 执行流程图解
```
排序后: [-4, -1, -1, 0, 1, 2]
i=0: nums[i]=-4, target=4
left=1,right=5: -1+2=1 < 4 → left++
left=2,right=5: -1+2=1 < 4 → left++
left=3,right=5: 0+2=2 < 4 → left++
left=4,right=5: 1+2=3 < 4 → left++
left=5,right=5: 结束
i=1: nums[i]=-1, target=1
left=2,right=5: -1+2=1 ✓ → [-1,-1,2]
left=3,right=4: 0+1=1 ✓ → [-1, 0,1]
i=2: nums[i]=-1, 与i=1相同 → skip
i=3: nums[i]=0, target=0
left=4,right=5: 1+2=3 > 0 → right--
left=4,right=4: 结束
```
# LeetCode 15. 三数之和 - C++ 实现
## 解题思路：排序 + 双指针
```
1. 对数组排序
2. 固定第一个数 nums[i]，双指针在 [i+1, n-1] 中找两数之和 = -nums[i]
3. 三处去重，避免重复三元组
```
**时间复杂度**: O(n²)
**空间复杂度**: O(log n)（排序栈空间）
---
## C++ 实现
```cpp
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
if (n < 3) return result;
sort(nums.begin(), nums.end()); // 排序
for (int i = 0; i < n - 2; i++) {
// ① 去重：跳过重复的第一个数
if (i > 0 && nums[i] == nums[i - 1])
continue;
// ② 剪枝：最小值 > 0，后面不可能有解
if (nums[i] > 0)
break;
int left = i + 1;
int right = n - 1;
int target = -nums[i]; // 需要找的两数之和
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.push_back({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;
}
};
```
---
## 测试代码
```cpp
#include <iostream>
int main() {
Solution sol;
// 测试用例 1
vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> res1 = sol.threeSum(nums1);
cout << "Test 1: ";
for (auto& v : res1) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: [-1, -1, 2] [-1, 0, 1]
cout << endl;
// 测试用例 2
vector<int> nums2 = {0, 1, 1};
vector<vector<int>> res2 = sol.threeSum(nums2);
cout << "Test 2: ";
for (auto& v : res2) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: (空)
cout << endl;
// 测试用例 3
vector<int> nums3 = {0, 0, 0};
vector<vector<int>> res3 = sol.threeSum(nums3);
cout << "Test 3: ";
for (auto& v : res3) {
cout << "[";
for (int j = 0; j < v.size(); j++) {
cout << v[j] << (j < v.size()-1 ? ", " : "");
}
cout << "] ";
}
// 输出: [0, 0, 0]
return 0;
}
```
---
## 关键要点总结
| 要点 | 说明 |
|------|------|
| 排序 | `sort(nums.begin(), nums.end())` |
| 剪枝 | `nums[i] > 0` 时直接 break，因为后面全是正数 |
| 去重① | `i > 0 && nums[i] == nums[i-1]` 跳过重复第一个数 |
| 去重②③ | 找到解后，left/right 跳过相同值再移动 |
| 边界 | `n < 3` 直接返回空 |
---
## 执行流程图解
```
排序后: [-4, -1, -1, 0, 1, 2]
i=0: nums[i]=-4, target=4
left=1,right=5: -1+2=1 < 4 → left++
left=2,right=5: -1+2=1 < 4 → left++
left=3,right=5: 0+2=2 < 4 → left++
left=4,right=5: 1+2=3 < 4 → left++
left=5,right=5: 结束
i=1: nums[i]=-1, target=1
left=2,right=5: -1+2=1 ✓ → [-1,-1,2]
left=3,right=4: 0+1=1 ✓ → [-1, 0,1]
i=2: nums[i]=-1, 与i=1相同 → skip
i=3: nums[i]=0, target=0
left=4,right=5: 1+2=3 > 0 → right--
left=4,right=4: 结束
```
