4.1 数组里的双指针
用暴力解法一定可解，双重循环得出结果。使用双指针的方法，可以借助一个额外变量，实现降维优化。 （1）相反方向运动
两个指针在数组的头和尾，都往中间移动，直到相遇。
两个指针在数组的中间，往数组的两端移动，直到到达边界。
每次循环时，我们值比较当前的两个元素，在这两个元素当中，求出对应的结果。
（2）相同方向运动
两个指针均在数组的一端，都往另一端移动，直到满足条件为止。
两个指针的移动速度不同，类似于滑动窗口问题，快指针一直往前遍历，走到尾部则循环结束，慢指针视条件进行移动。
每次循环时，看子区间是否满足某个条件，子区间是由双指针框起来， 输出的是子区间的变形。
4.2 双指针算法与前缀和
二者均是对子区间进行操作，因此有一定的结合可能。
前缀和是需要用到子区间和时，通过借助一个数组，去存储前缀和。
4.3 链表里的双指针
以快慢指针为主，快指针一次 2 步，慢指针一次 1 步等等。
典型例题：在链表当中找一个环，有环的话，快慢指针必定会相遇，若无环的话，则快指针就直接走到结尾。
1> 有序数组采用双指针 合并/查找...
| 题目 | 说明 | 实现 |
|---|---|---|
| 4. 寻找两个正序数组的中位数 | 两个数组中有序右移较小的元素指针，直到中点 | 我的提交 |
2> 夹逼定理，右指针负责探索正确解，左指针负责找最优,右指针每轮只移动一格
| 题目 | 说明 | 实现 |
|---|---|---|
| 633. 平方数之和 | 想象成二维数组，每一步都只是 排除一行左/一列下 的所有元素，从而不会漏掉目标元素 | 我的提交 |
| 1234. 替换子串得到平衡字符串 | 某一子串符合条件，则在该子串位置扩展的串也一定可以 | 我的提交 |
| 1839. 所有元音按顺序排布的最长子字符串 | 利用左右指针找到所有满足的最小区间 | 我的提交 |
3> 采用双指针 查找合法区间数目
| 题目 | 说明 | 实现 |
|---|---|---|
| 1248. 统计「优美子数组」 | 依次讨论每连续k个点所能形成的区间范围，左指针范围*右指针范围 | 我的提交 |
| 1358. 包含所有三种字符的子字符串数目 | 利用左右指针找到所有满足的最小区间，该区间右指针一直移到末尾的所有区间都满足条件 | 我的提交 |
| 2730. 找到最长的半重复子字符串 | 使用一个变量记录左指针应该移到的下一位置 | 我的提交 |
4> 头尾双指针
| 题目 | 说明 | 实现 |
|---|---|---|
| 1616. 分割两个字符串得到回文串 | 最终头尾一定是匹配的，中间可以不匹配，故采用头尾双指针 | 我的提交 |
5> 记录lastIdx保持窗口无重复
| 题目 | 说明 | 实现 |
|---|---|---|
| 1695. 删除子数组的最大得分 | lastIdx记录每个数上一次出现位置，每次l移到该位置即可 | 我的提交 |
| 题目 | 说明 | 题解 |
|---|---|---|
| 76. 最小覆盖子串 | 通过哈希表 needHash 判断滑动窗口包含了T的所有元素，使用 needCnt 免除每次遍历哈希表 🔥 | 滑窗 |
| 395. 至少有 K 个重复字符的最长子串 | 直接双指针无法解决，加入枚举目标串字符种类数 [1, 26]条件 就可以让区间具有二段性 🔥，另外可以用分治递归求解 |
宫水三叶 |
| 1004. 最大连续1的个数 III | 维护区间 0 的个数，找出一个最长的子数组，该子数组内最多允许有 K 个 0（正难则反） | 负雪明烛 |
| 1234. 替换子串得到平衡字符串 | 待替换子串之外的任意字符的出现次数都不能超过 m = n/4，维护区间外的字符出现次数 | 0x3F |
| 1438. 绝对差不超过限制的最长连续子数组 | 维护区间内最大值和最小值的差值，使用底层是红黑树的有序集合 multiset | 负雪明烛 |
| 1658. 将 x 减到 0 的最小操作数 | 和 2516 类似，逆向思考更直观，正向思考须分前缀后缀考虑 | 0x3F |
| 2379. 得到 K 个黑块的最少涂色次数 | 最基本的滑动窗口，窗口大小固定 | 通过 |
| 2516. 每种字符至少取 K 个 | 正向思考需要先考虑前缀为空，然后枚举前缀，反向思考更容易理解，直接滑动窗口取中间的字符至多x个 | 双指针 滑窗 |