★ 算法OJ题 ★ 力扣15 - 三数之和

Ciallo～(∠・ω< )⌒☆ ~ 本日，芝麻凛将和大家一起做一道双指针算法题--三数之和~

目录
一  标题
二  算法解析
三  编写算法

---

一  标题

15. 三数之和 - 力扣（LeetCode）

二  算法解析

解法一：排序 + 暴力罗列 + 使用set去重
时间复杂度：O(N^3)

解法二：排序 + 双指针

• 排序；
  
• 固定一个数C（C <= 0）；
  
• 在该数后面的区间内，使用双指针算法，快速找两个数的和为 -C。
  

这道题⾥⾯需要有去重操纵~

• 找到⼀个结果之后， left 和 right 指针要跳过重复的元素；
  
• 当使⽤完⼀次双指针算法之后，固定的 C 也要跳过重复的元素。
  

三  编写算法

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums)
4.     {
5.         vector<vector<int>> ret; // 存放结果的顺序表~
6.         sort(nums.begin(), nums.end());  // 排序~
7.         int n = nums.size();
8.         // 固定数i
9.         for (int i = 0; i < n; ) // i的变化需要跳过相同的数，放后面写~
10.         {
11.             if (nums[i] > 0) // 小优化，三个大于0的数加起来不可能等于0~
12.                 break;
13.             int left = i + 1, right = n - 1, target = -nums[i];
14.             while (left < right)
15.             {
16.                 // 两数之和
17.                 int sum = nums[left] + nums[right];
18.                 if (sum == target)
19.                 {
20.                     ret.push_back({ nums[i], nums[left], nums[right] });
21.                     left++;
22.                     right--;
23.                     // 去重，left right 跳过相同数，但不能越界
24.                     while (left < right && nums[left] == nums[left - 1])
25.                         left++;
26.                     while (left < right && nums[right] == nums[right + 1])
27.                         right--;
28.                 }
29.                 if (sum < target)
30.                     left++;
31.                 if (sum > target)
32.                     right--;
33.             }
34.             i++;
35.             // 去重，i 跳过相同数，但不能越界
36.             while (i < n && nums[i] == nums[i - 1])
37.                 i++;
38.         }
39.         return ret;
40.     }
41. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。