# 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: 结束

```