【C++算法】8.双指针_三数之和
文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解
题目链接：
15.三数之和
题目描述：
解法
解法一：排序+暴力枚举+利用set去重O(n3)
例如
nums=[-1，0，1，2，-1，-4]
[-1，0，1]和[0，1，-1]和[1，0，-1]下标不同但是都满足 ，这个题难在去重。可以通过排序去重，先把数组排序再找，就不会出现上面一行出现的问题了。
但是这里举例的
nums里面由两个-1，可能会出现[-1，0，1]两次。这个就可以通过set容器去除。
解法二：排序+双指针
- 先排序
- 固定一个数
a- 在该数后面的区间内，利用双指针算法快速找到两个数的和等于
-a处理细节：
去重
找到一种结果之后，
left和right指针要跳过重复元素当使用完一次双指针算法之后，
i也要跳过重复元素不漏掉
找到一种结果后，不要停，缩小区间，继续寻找
C++ 算法代码：
class Solution
{public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;//用ret记录结果// 1. 排序sort(nums.begin(), nums.end());// 2. 利用双指针解决问题int n = nums.size();for(int i = 0; i < n; ) // 固定数 a{if(nums[i] > 0){break; // 小优化}int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target){right--;}else if(sum < target){left++;}else{//说明找到最终结果ret.push_back({nums[i], nums[left], nums[right]});//把三个数放到ret里面，{}会形成一个vector int的数组放到ret里面left++, right--;// 去重操作 left 和 rightwhile(left < right && nums[left] == nums[left - 1]){left++;}while(left < right && nums[right] == nums[right + 1]){right--;}}}i++;// 去重 iwhile(i < n && nums[i] == nums[i - 1]){i++;}}return ret;}
};
图解
nums=[-4，-4，-1，0，0，0，1，1，4，4，5，6]
n=12，进入for循环，i=0，left=1，right=11，target=4，left < right进入while循环，sum=2<target，left++
sum=-1+6=5>target，right--
sum=-1+5=4=targe，把[-4，-1，5]放到ret里面，left++, right--
sum=0+4=4=targe，把[-4，0，4]放到ret里面，left++, right--，执行去重操作
sum=1+1=2<targe，left++，跳出while循环，i++，执行去重，然后开始第二轮双指针算法。
- 后面的步骤类似，就不多赘述了。