本文主要是介绍★ 算法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;}
};
这篇关于★ 算法OJ题 ★ 力扣15 - 三数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
