这一篇博客也用了双指针算法，同学们可以参考一下
代码随想录算法训练营第一天 | 题目2（LeetCode27移除元素）_小吉.cpp的博客-CSDN博客
老实说，双指针算法，顾名思义，就是两个指针，其实是一种优化方式
下面的题目大家看代码和注释就能理解了
🚥🚥🚥
799. 最长连续不重复子序列 - AcWing题库
蓝色的箭头是 i
红色的箭头是 j
代码
#include <iostream> using namespace std; const int N = 100010; int a[N], count[N]; int n, ans; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0, j = 0; j < n; j++) { count[a[j]] ++; while (count[a[j]] > 1) { //注意是>1,不是>=1 当count=1时，不会-- count[a[i]] --; i++; } ans = max(ans, j - i + 1); } printf("%d", ans); return 0; }
#include <iostream> using namespace std; const int N = 1e5 + 10; int n, m, x; int a[N], b[N]; int main() { scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]); for (int i = 0, j = m - 1; i < n; i ++ ) //j=m-1 { while (j >= 0 && a[i] + b[j] > x) j -- ; //移动j指针 if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl; //移动i指针 } return 0; }
这个while循环使用的特别妙
#include <iostream> #include <cstring> using namespace std; const int N = 100010; int n, m; int a[N], b[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]); int i = 0, j = 0; while (i < n && j < m) { if (a[i] == b[j]) i ++ ;//匹配上 j ++ ; //没有匹配上 } if (i == n) puts("Yes"); else puts("No"); return 0; }
#include <iostream> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 100010; int n, d, k, cnt[N]; //用于存储每个id号获得赞数，所以后面代码为cnt[t] ++ PII logs[N]; bool st[N]; // 记录每个帖子是否是热帖 int main() { scanf("%d%d%d", &n, &d, &k); for (int i = 0; i < n; i ++ ) scanf("%d%d", &logs[i].first, &logs[i].second); sort(logs, logs + n); for (int i = 0, j = 0; i < n; i ++ ) { int id = logs[i].second;//加入新的帖子 cnt[id] ++ ;//获得一个赞 while (logs[i].first - logs[j].first >= d)//两个帖子的时间跨度如果>=d,那么这个赞无效 { cnt[logs[j].second] -- ;//删除这个id j ++ ;//指针移动 } if (cnt[id] >= k) st[id] = true;//当前id是否>=k,如果>=k,那么就是热帖 } for (int i = 0; i <= 100000; i ++ ) if (st[i]) printf("%d\n", i); return 0; }
1031-组队_牛客竞赛语法入门班数组模拟、枚举、贪心习题 (nowcoder.com)
在下面的代码中，有一步while(r<=n&&a[r]-a[l]<=k) r++;
为什么会一直r++,并且r不会每次都变为0
其实就是因为已经是排好顺序的，
+a[l]是小于a[r]的，每次l++,大的数满足<=k,小的数一定满足<=k
#include <iostream> #include <algorithm> using namespace std; int a[200005],b[200005]; int main() { int t; cin>>t; int n,k; while(t--){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int l=1,r=1; int res=0; for(;l<=n;l++){ while(r<=n&&a[r]-a[l]<=k) r++; res=max(res,r-l); } cout<<res<<endl; } }
下面这道题有点迷惑人，有意思
1027-字符串_2021秋季算法入门班第一章习题：模拟、枚举、贪心 (nowcoder.com)
小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。
一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。（就是26个字母）
小N希望知道所有的合法的S的子串中，长度最短是多少。
// 尺取法 #include<iostream> #include<string> using namespace std; int a[27] = {0}; int main(){ string s; cin >> s; int len = s.length(); int minLength = len+1, c=0; for(int i=0, j=0; i<len; i++){ if(a[s[i] - 'a'] == 0){//字母 c++; } a[s[i] - 'a']++; while(a[s[j] - 'a'] > 1){ a[s[j] - 'a']--; j++; } if(c == 26){ minLength = min(minLength, i-j+1); } } cout<<minLength<<endl; return 0; }
Code over!
