预计阅读时间：5 分钟
滑动窗口和双指针
双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。
分组循环
同向双指针的一种特殊形态：左端点 start 只在每组开头记一次，右端点就是循环变量 i 本身，组与组之间不回退。
适用场景
数组会被切成若干组，每一组的处理逻辑相同。
核心思想
外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。
模板
n = len(nums)
i = 0
while i < n:
start = i
i += 1 # a group has at least one element, so i always advances
while i < n and ...: # usually compares nums[i] with nums[i - 1]
i += 1
# nums[start..i-1] is one group
# the next group starts at i, no extra i += 1 needed
进内层循环前先 i += 1：每组至少有一个元素，这样外层每一轮 i 至少前进一步。如果省掉这一步，内层条件在 i == start 时就不成立的话，i 不动，外层会死循环。下面两题的代码都是这个形状。
题目
leetcode 978
判断湍流性质要连看三个数：组能从 arr[i] 延伸到 arr[i+1]，当且仅当 (arr[i] - arr[i-1]) 和 (arr[i+1] - arr[i]) 异号，即乘积小于 0。两点细节：
- 相邻两组共用一个端点：一组在
arr[i]处断开时，arr[i]仍可以是下一组的起点，所以下一组从 i 开始，不跳过它； - 相等的相邻元素不能开组，遇到就单独前进一步。
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
ans = 1
i = 0
while i < n - 1:
if arr[i] == arr[i + 1]: # equal pair cannot start a group
i += 1
continue
start = i
i += 1
while i < n - 1 and (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]) < 0:
i += 1
# arr[start..i] is turbulent; the next group starts at i
ans = max(ans, i - start + 1)
return ans
leetcode 3255
题目要求窗口里的数连续且升序（每个比前一个大 1），只是严格上升不够：[1,3,5]、k = 3 的答案是 [-1]。先用分组循环把数组切成若干段，每段内相邻元素差恰好为 1。长度为 k 的窗口逐格滑动、互相重叠：完全落在某一段里的窗口，最大值就是它的最后一个元素；跨段的窗口答案都是 -1。所以在每段里，以段内第 k 个及之后元素结尾的窗口填上该元素，其余保持 -1。如果没有「连续上升」这个前提，滑动窗口求最大值就要上单调双端队列来维护了。
class Solution:
def resultsArray(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
ans = [-1] * (n - k + 1)
i = 0
while i < n:
start = i
i += 1
while i < n and nums[i] == nums[i - 1] + 1:
i += 1
# nums[start..i-1] is a consecutive ascending run
for end in range(start + k - 1, i):
ans[end - k + 1] = nums[end]
return ans
leetcode 467
题意很绕，需要仔细读。要找的子串里，每个字母都是前一个字母的下一个，z 后面接 a（za 也合法），难点在如何统计去重。关键观察：起始字母相同时，长的合法子串一定完全覆盖短的，以某字母开头的合法子串总数就等于以它开头的最长长度。怎么求「以它开头的最长长度」：用分组循环把字符串切成若干个最长段，段内相邻字母依次相连（z 接 a），段 [start, i-1] 里位置 j 开头的最长长度是 i - j。于是按 26 个起始字母分组，每组取最长值，累加即为答案。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。