预计阅读时间：3 分钟

滑动窗口和双指针

双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。

分组循环

同向双指针的一种特殊形态，可以省掉一个显式指针。

适用场景

数组会被切成若干组，每一组的处理逻辑相同。

核心思想

外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。

模板

n = len(nums)
i = 0
while i < n:
    start = i
    while i < n and ...:
        i += 1
    # 从 start 到 i-1 是一组
    # 下一组从 i 开始，无需 i += 1

题目

leetcode 978

判断湍流性质要连看三个数，相等的数需要跳过成组。注意最后答案的计算方式：这一组可能包含位置 i，也可能不包含（i 已越界）。

leetcode 3255

先找出长度不小于 k 的最长严格上升子数组，再在其中按窗口分组。因为已保证上升，每个窗口的最大值就是最后一个元素。如果没有「上升」这个前提，滑动窗口求最大值就要上单调双端队列来维护了。

leetcode 467

题意很绕，需要仔细读。要找的子串是按字母表严格循环递增的，难点在如何统计去重。关键观察：起始字母相同时，长的合法子串一定完全覆盖短的，以某字母开头的合法子串总数就等于以它开头的最长长度。于是按 26 个起始字母分组，每组取最长值，累加即为答案。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。