LeetCode Hot100【双指针-15. 三数之和】

题目：15. 三数之和

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         vector<vector<int>> result;  // 存储符合条件的三元组
5.         sort(nums.begin(), nums.end());
6.   // 先排序
8.         for (int i = 0; i < nums.size(); ++i) {
9.             if (nums[i] > 0) {
10.                 return result;  // 因为已排序，nums[i] > 0 时，后续不可能再有和为 0 的三元组
11.             }
12.             if (i > 0 && nums[i] == nums[i - 1]) {
13.                 continue;  // 跳过重复元素，避免结果重复
14.             }
15.             
16.             int left = i + 1;
17.             int right = nums.size() - 1;
19.             while (right > left) {
20.                 int sum = nums[i] + nums[left] + nums[right];
22.                 if (sum > 0) {
23.                     --right;  // 如果和大于 0，说明 `right` 过大，右指针左移
24.                 }
25.                 else if (sum < 0) {
26.                     ++left;  // 如果和小于 0，说明 `left` 过小，左指针右移
27.                 }
28.                 else {
29.                     result.push_back(vector<int>{nums[i], nums[left], nums[right]});  // 记录有效的三元组
31.                     // 跳过重复 `right`
32.                     while (right > left && nums[right] == nums[right - 1]) {
33.                         --right;
34.                     }
35.                     // 跳过重复 `left`
36.                     while (right > left && nums[left] == nums[left + 1]) {
37.                         ++left;
38.                     }
39.                     --right;
40.                     ++left;
41.                 }
42.             }
43.         }
44.         return result;
45.     }
46. };

复制代码

执行流程

1. nums = {-1, 0, 1, 2, -1, -4};

复制代码

排序后

1. nums = {-4, -1, -1, 0, 1, 2}

复制代码

执行步骤如下：

i (固定数)leftright三元组是否记载-4 (i = 0)-1 (1)2 (5)-4 + (-1) + 2 = -3❌-4 (i = 0)0 (3)2 (5)-4 + 0 + 2 = -2❌-4 (i = 0)1 (4)2 (5)-4 + 1 + 2 = -1❌-1 (i = 1)-1 (2)2 (5)-1 + (-1) + 2 = 0✅ 记载 {-1, -1, 2}-1 (i = 1)0 (3)1 (4)-1 + 0 + 1 = 0✅ 记载 {-1, 0, 1}0 (i = 3)1 (4)2 (5)0 + 1 + 2 = 3❌ 最终返回

1. {{-1, -1, 2}, {-1, 0, 1}}

复制代码

时间 & 空间复杂度

操纵时间复杂度空间复杂度排序 numsO(nlogn)O(1)遍历 numsO(n)O(1)双指针 left & rightO(n)O(1) 最终

• 时间复杂度：O(n2)（排序 + 双指针）
  
• 空间复杂度：O(1)（效果 vector 不计入额外空间）
  

优化 & 变种

利用 unordered_set 存储已遍历的 nums

1. vector<vector<int>> threeSum(vector<int>& nums) {
2.     unordered_set<int> seen;
3.     sort(nums.begin(), nums.end());
5.     vector<vector<int>> result;
7.     for (int i = 0; i < nums.size(); ++i) {
8.         if (seen.count(nums[i])) continue;
9.         seen.insert(nums[i]);
11.         int left = i + 1, right = nums.size() - 1;
13.         while (left < right) {
14.             int sum = nums[i] + nums[left] + nums[right];
16.             if (sum == 0) {
17.                 result.push_back({nums[i], nums[left], nums[right]});
18.                 while (left < right && nums[left] == nums[left + 1]) ++left;
19.                 while (left < right && nums[right] == nums[right - 1]) --right;
20.                 ++left; --right;
21.             } else if (sum < 0) {
22.                 ++left;
23.             } else {
24.                 --right;
25.             }
26.         }
27.     }
28.     return result;
29. }

复制代码

unordered_set 进一步减少重复盘算。

---

基础知识

1. sort(nums.begin(), nums.end())

1. sort(nums.begin(), nums.end());

复制代码

• 排序 nums，确保双指针法正确执行。
  
• O(n log n) 复杂度。
  

2. 跳过重复元素

1. if (i > 0 && nums[i] == nums[i - 1]) {
2.     continue;
3. }

复制代码

• 避免重复盘算，保证效果唯一性。
  

3. 双指针 left & right

1. int left = i + 1, right = nums.size() - 1;

复制代码

• 固定 nums，双指针 left 和 right 查找剩余两个数。
  

4. 盘算三数之和

1. int sum = nums[i] + nums[left] + nums[right];

复制代码

• 如果 sum > 0，阐明 right 过大，right–。
  
• 如果 sum < 0，阐明 left 过小，left++。
  
• 如果 sum == 0，存入效果，并移动 left 和 right。
  

5. 跳过重复 left 和 right

1. while (right > left && nums[right] == nums[right - 1]) {
2.     --right;
3. }
4. while (right > left && nums[left] == nums[left + 1]) {
5.     ++left;
6. }

复制代码

• 跳过相同的 left 和 right，避免效果重复。
  

总结

C++语法作用sort(nums.begin(), nums.end())先排序，确保双指针法有效if (i > 0 && nums == nums[i - 1]) continue;C++ 动态数组unordered_map<int, int>跳过重复 numswhile (left < right)双指针法if (sum == 0)记载三元组while (nums[left] == nums[left + 1]) left++;跳过重复元素