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

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

目录

一  题目

二  算法解析

三  编写算法

---

一  题目

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

二  算法解析

解法一：排序 + 暴力枚举 + 利用set去重

时间复杂度：O(N^3)

解法二：排序 + 双指针

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

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

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

三  编写算法

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums){vector<vector<int>> ret; // 存放结果的顺序表~sort(nums.begin(), nums.end());  // 排序~int n = nums.size();// 固定数ifor (int i = 0; i < n; ) // i的变化需要跳过相同的数，放后面写~{if (nums[i] > 0) // 小优化，三个大于0的数加起来不可能等于0~break;int left = i + 1, right = n - 1, target = -nums[i];while (left < right){// 两数之和int sum = nums[left] + nums[right];if (sum == target){ret.push_back({ nums[i], nums[left], nums[right] });left++;right--;// 去重，left right 跳过相同数，但不能越界while (left < right && nums[left] == nums[left - 1])left++;while (left < right && nums[right] == nums[right + 1])right--;}if (sum < target)left++;if (sum > target)right--;}i++;// 去重，i 跳过相同数，但不能越界while (i < n && nums[i] == nums[i - 1])i++;}return ret;}
};