双指针

模板

参考

参考2

定长滑动窗口

todo

不定长滑动窗口

分为求最长/最大 和求最短/最小。

枚举右端点，不断将左端点增加。更新结果的操作可以根据题意可以放进里面的while里

def findSubstring(s):
    N = len(s) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    counter = collections.Counter() # 用于统计 子数组/子区间 是否有效
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        counter[s[right]] += 1 # 增加当前右边指针的数字/字符的计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            counter[s[left]] -= 1 # 移动左指针前需要从counter中减少left位置字符的计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

不定长滑动窗口（求子数组个数）

多指针滑动窗口

相向双指针

应用

1. 统计子数组数目，枚举右边界，左边界视情况而定。比如求子数组数目，要求子数组包含两个值，那枚举i，j就等于有两个值的最后最小坐标，每次结果可加i-j+1, 实例题目 6207. 统计定界子数组的数目 题解

2. 3Sum 排序+双指针

3. Longest Repeating Character Replacement 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

   解答: 双指针。这个双指针属于left每次只移动一次，记得看下。

4. 11. 盛最多水的容器 多个柱子，挑两个柱子，统计最多能接多少水，双指针，不断缩小两边矮的那个

5. 1438. 绝对差不超过限制的最长连续子数组 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。 维护max, min的队列，同时双指针，不断移动左指针。

6. 6270. 每种字符至少取 K 个 给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

   你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数

7. 1658. 将 x 减到 0 的最小操作数

8. 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

   如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

   反向思考，找最大子数组。