【OJ刷题】双指针问题5

这里是阿川的博客，祝您变得更强

✨ 个人主页：在线OJ的阿川
💖文章专栏：OJ刷题入门到进阶
🌏代码仓库：

写在开头

现在您看到的是我的结论或想法，但在这背后凝结了大量的思考、经验和讨论

在这里插入图片描述

1. 题目介绍

难度：中
题目练习：三数之和
题目信息：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
举个例子： 具体如图1所示

图1 举个例子

2. 题目拆解

本质上：观察规律，双指针遍历判断
特点是：在组合搭配中有一定规律
解决方法：双指针算法，如图2所示

图2 双指针

3. 具体详情

1. 先进行排序
2. 固定一个数a，且固定时跳过重复固定值且该固定数大于小于0即可
3. 在该数后面的区间内，利用"双指针算法"遍历完整个数组找到两个的和等于-a即可，且在过程中找到一种结果之后，双指针要跳过重复元素，直到双指针相遇

4. 具体代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());vector<vector<int>> cur;int n = nums.size();// 固定值并移动，双指针具体实现for(int i = 0; i < n ;){// 固定值大于0则双指针中不可能出现符合题目要求的可能if(nums[i] > 0) break;int left = i + 1, right = n - 1;// 利用"双指针算法"遍历完整个数组找到两个的和等于-固定值while(left < right){if(nums[left] + nums[right] > -nums[i]) right--;else if(nums[left] + nums[right] < -nums[i]) left++;else{cur.push_back({nums[i], nums[left], nums[right]});left++, right--;// 双指针要跳过重复元素，直到双指针相遇while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}i++;// 固定时跳过重复固定值while(i < n && nums[i] == nums[i - 1]) i++;}return cur;}
};