# LeetCode 15. 三数之和 - C 实现## 解题思路排序 双指针1. 对数组排序2. 固定第一个数 nums[i]双指针在 [i1, n-1] 中找两数之和 -nums[i]3. 三处去重避免重复三元组**时间复杂度**: O(n²)**空间复杂度**: O(log n)排序栈空间---## C 实现cpp#include vector#include algorithmusing namespace std;class Solution {public:vectorvectorint threeSum(vectorint nums) {vectorvectorint 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 iostreamint main() {Solution sol;// 测试用例 1vectorint nums1 {-1, 0, 1, 2, -1, -4};vectorvectorint 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;// 测试用例 2vectorint nums2 {0, 1, 1};vectorvectorint 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;// 测试用例 3vectorint nums3 {0, 0, 0};vectorvectorint 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]i0: nums[i]-4, target4left1,right5: -121 4 → leftleft2,right5: -121 4 → leftleft3,right5: 022 4 → leftleft4,right5: 123 4 → leftleft5,right5: 结束i1: nums[i]-1, target1left2,right5: -121 ✓ → [-1,-1,2]left3,right4: 011 ✓ → [-1, 0,1]i2: nums[i]-1, 与i1相同 → skipi3: nums[i]0, target0left4,right5: 123 0 → right--left4,right4: 结束# LeetCode 15. 三数之和 - C 实现## 解题思路排序 双指针1. 对数组排序2. 固定第一个数 nums[i]双指针在 [i1, n-1] 中找两数之和 -nums[i]3. 三处去重避免重复三元组**时间复杂度**: O(n²)**空间复杂度**: O(log n)排序栈空间---## C 实现cpp#include vector#include algorithmusing namespace std;class Solution {public:vectorvectorint threeSum(vectorint nums) {vectorvectorint 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 iostreamint main() {Solution sol;// 测试用例 1vectorint nums1 {-1, 0, 1, 2, -1, -4};vectorvectorint 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;// 测试用例 2vectorint nums2 {0, 1, 1};vectorvectorint 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;// 测试用例 3vectorint nums3 {0, 0, 0};vectorvectorint 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]i0: nums[i]-4, target4left1,right5: -121 4 → leftleft2,right5: -121 4 → leftleft3,right5: 022 4 → leftleft4,right5: 123 4 → leftleft5,right5: 结束i1: nums[i]-1, target1left2,right5: -121 ✓ → [-1,-1,2]left3,right4: 011 ✓ → [-1, 0,1]i2: nums[i]-1, 与i1相同 → skipi3: nums[i]0, target0left4,right5: 123 0 → right--left4,right4: 结束