优选算法——双指针专题7（单调性）
🔥近津薪荼：个人主页
🎬个人专栏：《c语言基础知识详解》《c++基础知识详解》《Linux操作系统及网络基础知识分享》《近津薪荼的算法日迹》
✨有利的情况和主动的恢复，产生于‘再坚持一下’的努力之中
本期知识点导图：
1.上期参考代码
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { int n=price.size(); int left=0; int right =n-1; while(left<right) { if(price[left]+price[right]==target) return {price[left],price[right]}; else if(price[left]+price[right]<target) left++; else right--; } return {};//找不到要返回空 } };不会有人没敲出来吧
2.题目解析
要点:
要去重
三元组的元素之和为0
随机数组找三元组
眼熟不
3解题思路：
3.1暴力解法
- 先用sort接口将原数组排序
当数组呈升序，方便后边的去重操作（重复元素相邻） - 遍历所有三元组，找到满足条件的三元组，通过push_back接口，放到ret中去
- 不管是暴力解还是优解，都要进行去重操作
class Solution { public: vector<vector<int>> hajiminanbeilvdou(vector<int>& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); vector<vector<int>> ret; for(int i = 0; i < n - 2; i++) { // 去重i if(i > 0 && nums[i] == nums[i-1]) continue; for(int j = i + 1; j < n - 1; j++) { // 去重j if(j > i + 1 && nums[j] == nums[j-1]) continue; for(int k = j + 1; k < n; k++) { // 去重k if(k > j + 1 && nums[k] == nums[k-1]) continue; if(nums[i] + nums[j] + nums[k] == 0) { ret.push_back({nums[i], nums[j], nums[k]}); } } } } return ret; } };该解法的时间复杂度是O(N^3)，会超时
3.2双指针解法
3.2.1.先排序
为了方便后面的去重以及双指针的遍历（都依赖于数组的单调性）
3.2.2找三元组：采用for+双指针（把时间复杂度干到O(N^2)）
进入for循环，先固定一个数，然后取反
接下来就是找两数之和（O(N)）的操作了：找两数之和等于取反之后的值
忘了的同学传送门在这里：两数之和
3.3.3去重
同暴力解法的去重操作思路相同，遍历时跳过相同元素
注意
当出现极端情况，一直跳过相同元素，可能会造成数组访问越界，比如说数组长度为4,4个元素全是0，思考一下如何解决这个问题。
思路讲解就到这里了
劝敲：
本题一定一定要自己动手敲一遍，一是运用到的知识点包含了前两天的主要内容，起到复习巩固的作用，二是本题难度不大，但是很锻炼代码能力，所以大家自己动手写一遍，再看下一期的参考代码，特别是新手同学，不写的通通击毙
。
4.预告
下期要讲的题目是：
明天还会再见的，对吗
