双指针（同向双指针）
145 字
1 分钟
双指针（同向双指针）
- 核心思想 right 一直往右走（不回退） left 只在“窗口非法”时被迫右移（也不回退）
- 时间优化：两层for->一层while;
- 模板（最长合法窗口）
int left = 0, ret = 0;unordered_map<int,int> mp; // 计数器，视题意更换for (int right = 0; right < n; ++right) { // 1. 进窗口 mp[a[right]]++;
// 2. 判断合法性 while (mp[a[right]] > 1) { // 出现重复，非法 // 3. 出窗口 mp[a[left]]--; left++; }
// 4. 更新答案 ret = max(ret, right - left + 1);}- 常见题型
- 最长无重复子串
- 最长至多k个重复子串
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
算法错题本
算法在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
2
数论
算法如果 $a$ 除以 $b$ 没有余数，那么 $a$ 就是 $b$ 的倍数，$b$ 就是 $a$ 的约数，记作 $b \mid a$。 约数，也称因数。
3
高精度
算法当数据的值特别大，超出各种基本数据类型的存储范围时，需要使用高精度算法来计算加减乘除。
4
分治
算法问题一分为二 —递归(DFS)-合并答案 时间优化：O(nn)-O(n log n)
5
贪心
算法思路 猜一个排序依据（比如按重量、按 deadline、按权值差等） 任取相邻两项 i, j 假设顺序错了，写出交换前/后只与这两头有关的代价/收益表达式 令“交换后更优”得不等式，化简成key(i) key(j)这个 key 就是 so…
随机文章随机推荐