双指针two‑pointer双指针用两个变量代表两个下标不嵌套两层循环把O ( n 2 ) O(n^2)O(n2)优化到 (O(n))。分为两大类对撞双指针、滑动窗口快慢指针。一、两种双指针模型1. 对撞双指针左右指针l 0r n‑1一个在最左一个在最右向中间靠拢。前提条件数组有序经典两数之和、三数之和、判断回文、反转数组。模板intl0,rn-1;while(lr){if(条件){l;}else{r--;}}2. 滑动窗口快慢指针 / 同向双指针两个指针都从左边出发都向右走l窗口左边界r窗口右边界。维持区间KaTeX parse error: Cant use function \( in math mode at position 1: \̲(̲[l,r]\)满足/不满足条件。常用于子数组、子串问题。模板求满足条件的最长子区间intl0;for(intr0;rn;r){//把a[r]加入窗口while(窗口不满足条件){//移动左指针收缩窗口l;}//此时 \([l,r]\) 合法更新答案ansmax(ans,r-l1);}模板求满足条件最短子区间intl0;for(intr0;rn;r){//加入a[r]while(窗口满足条件){ansmin(ans,r‑l1);l;}}二、使用场景对撞双指针数组有序有序数组两数之和找 (a[l]a[r]target)167. 两数之和 II - 输入有序数组 - 力扣LeetCode一键直达167判断回文字符串判断回文字符串一键直达判断回文字符串归并排序合并两个有序数组三数之和、四数之和去重同向滑动窗口子数组/子串适合所有元素都是正数区间和具有单调性或者统计字符出现次数。最长无重复字符子串3. 无重复字符的最长子串 - 力扣LeetCode一键直达3和大于等于target的最短子数组209. 长度最小的子数组 - 力扣LeetCode 581. 最短无序连续子数组 - 力扣LeetCode一键直达209 581最多k种字符的最长子串P1638 逛画展 - 洛谷一键直达P1638求满足条件子数组数量S的子数组数量 S的子数组数量 P1147 连续正整数和 - 洛谷一键直达S的子数组数量 S的子数组数量 P1147⚠重要坑如果数组有负数滑动窗口不能直接用没有单调性要用前缀和哈希。三、经典例题对撞指针** 例题1——有序数组两数之和**167. 两数之和 II - 输入有序数组 - 力扣LeetCode题目大意找到两个数相加为目标值返回这两个数的下标思路双指针二分双指针左右夹击左右两值相加大于目标值右指针左移让值变小反之左指针右移#include vector using namespace std; class Solution { public: vectorint twoSum(vectorint numbers, int target) { int left 0, right numbers.size() - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { // 题目要求返回的下标从1开始 return {left 1, right 1}; } else if (sum target) { left; } else { right--; } } return {}; // 题目保证有解这行仅为语法完整 } };42. 接雨水 - 力扣LeetCode题目大意找到在这样的积木下能装下多少面积的水思路双指针单调栈找当前判断的左右边高度中较小的那边当前高度比较低那边的最大高度要高时更新最大高度反之用最大高度减去当前高度就是能留下的水的面积指针走到下一个位置#includebits/stdc.h using namespace std; int main() { int n; cinn; int l0,rn-1; int l_max0,r_max0; int w0; vectorint h(n); for(int i0;in;i) { cinh[i]; } while(lr) { if(h[l]h[r])//在两块挡边之间只能采用短板效应 { if(h[l]l_max) l_maxh[l]; else wl_max-h[l];//作为夹在左右最高挡板之间的挡板这是他能存的水 l; } else { if(h[r]r_max) r_maxh[r]; else wr_max-h[r]; r--; } } coutwendl; }例题2判断回文串对撞指针判断回文字符串boolisPalindrome(string s){intl0,rs.size()-1;while(lr){if(s[l]!s[r])returnfalse;l;r--;}returntrue;}滑动窗口例题1最长无重复字符子串3. 无重复字符的最长子串 - 力扣LeetCode题目大意找出连续且不重复的最长连续子字符串思路用两个指针左指针看右指针是否重复右指针遍历字符串若存在过且左指针小于等于右指针把左指针定位到这个重复位置把每个字符放进map中更新子字符串的长度#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; void slove(){ string s; cins; mapchar,intmp; int left0; int max10; for(int right0;rights.size();right){ int cs[right];//遍历字符串的每个字符 if(mp.count(c)leftright){ leftmp[c]1;//当遇到重复字符时左边界变为之前存入的重复字符的位置 //开始算新字符串的边界 因此不用考虑mp中存入的重复字符还在其中 //如果下面的字符还有之前出现过的那边会从重复字符那里开始算新的字符串长度 } mp[c]right;//字符在字符串中的位置 max1max(max1,right-left1); } coutmax1endl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }例题2长度最小的子数组209. 长度最小的子数组 - 力扣LeetCode题目大意给定全部正数数组找和≥target的最短子数组长度。#includebits/stdc.h using namespace std; int main(){ int n,target; cinntarget; vectorinta(n); for(int i0;in;i) cina[i]; int l0,sum0; int ans1e9; 【遍历数组记录每一个满足target的数组长度】 for(int r0;rn;r){ suma[r]; while(sum target){ ansmin(ans,r‑l1); sum-a[l]; l; } } if(ans1e9) cout0; else coutans; return 0; }581. 最短无序连续子数组 - 力扣LeetCode题目大意:找到最短且连续的无序子数组思路双指针排序贪心单调栈让排序后的数组和原数组比较移动左右指针直到左右两边都遇到不相等的#include vector #include algorithm using namespace std; class Solution { public: int findUnsortedSubarray(vectorint nums) { vectorint sorted nums; sort(sorted.begin(), sorted.end()); int left 0, right nums.size() - 1; // 找左边第一个和排序后不同的位置 while (left nums.size() nums[left] sorted[left]) { left; } // 找右边第一个和排序后不同的位置 while (right 0 nums[right] sorted[right]) { right--; } // 数组已经有序 if (left right) return 0; return right - left 1; } };例题3最多k种字符的最长子串P1638 逛画展 - 洛谷题目大意找到这段数组中最先出现的连续包含m种数字的最长子数组思路二分双指针单调队列用桶思想将出现过的每一种编号个数统计起来每多一种画家就多一位当所有画家的编号都被统计过记录当下的左右指针此时看看能不不能更小的长度让左边去掉指针右移#includebits/stdc.h using namespace std; int n,m,a[1000005],b[2005],k,ans,l,r,ll,rr; //b[i]表示当前区间画家i的图画数 int main() { scanf(%d%d,n,m); for(int i1;in;i) scanf(%d,a[i]); l1; r1; k1; b[a[1]]1; ans1000005; //k记录当前区间中有多少画家的图画 while(lr rn) { if(km)//判断是否符合要求 { if(ansr-l1) { ansr-l1;//ans记录最小区间长度 lll; rrr; //ll记录最小区间的左端点,rr记录最小区间的右端点 } b[a[l]]--; if(b[a[l]]0) k--; l; } else{ r; b[a[r]]; if(b[a[r]]1) k; } } printf(%d %d,ll,rr); return 0; }例题4求满足条件子数组数量l:满足S的左边界s:满足S的右边界ans:满足S的子数组的数量sum:当前l-r区间的和S的子数组数量题目大意给定全为正整数的数组a求有多少个子数组满足子数组和 ≤ S#includebits/stdc.h using namespace std; #define int long long int main() { int n,S; cinnS; vectorinta(n); for(int i0;in;i) cina[i]; int l0; int sum0; int ans0; for(int r0;rn;r) { sum a[r]; // 窗口和超过S收缩左边界 while(sum S) { sum - a[l]; l; } // [l ... r]全部合法以r为右端点的子数组数量 ans r - l 1; } coutansendl; return 0; }S的子数组数量题目大意子数组和 ≥ S统计子数组数目正数数组//总的子数组数量 int total n*(n1)/2; int less_cnt 0; int l0,sum0; for(int r0;rn;r){ suma[r]; while(sum S){ sum-a[l]; l; } less_cnt r-l1; } int ans total - less_cnt;P1147 连续正整数和 - 洛谷题目大意给定 M求有多少组连续自然数之和等于 M。void slove(){ int m; cinm; int l1; int cur_sum0; vectorpiiv; // 至少两个数r最大到(m1)/21 for(int r1; r (m1)/21; r){ cur_sum r; while(cur_sum m){ cur_sum - l; l; } if(cur_sum m){ v.push_back({l, r}); cur_sum - l; l; } } for(auto c:v){ coutc.fi c.seendl; } }四、考试记忆总结对撞双指针有序左右两头往中间跑适合求和、回文。同向滑动窗口两个指针都向右窗口[ l , r ]求子数组子串。对比对撞l↑r↓相向而行。滑动窗口l↑r↑同向而行。