双指针
01 / 共享的机制
两个下标在同一序列上移动以维持某个 不变式 — 移动规则在子模式间各不相同, 但底层机制是相通的。
02 / 一句话本质
当你需要一段满足条件的连续区间时, 从右侧扩张直到条件破坏,然后 从左侧收缩直到条件再次成立。
题目和 ≤ k 的最长子数组输入[3, 1, 2, 1, 4, 2, 1, 5]k8
30
11
22
13
44
25
16
57
准备就绪。按 play 从右侧开始扩张窗口。
步
0 / 27
窗口和
0
当前长度
0
目前最优
0
0 / 27
03 / 模式骨架
# 一条序列上的两个下标left, right ← 0while right < n:// 1. 扩张窗口将 arr[right] 纳入状态while 不变式被破坏:移除 arr[left]; left++// 2. 记录当前合法窗口best ← max(best, right − left + 1)right++
04 / 什么时候用这个模式
"连续区间"
答案是数组的一段切片,而不是子集。 如果可以重排,这就不是合适的工具。
"最长 / 最短"
你在约束下优化这段连续切片的长度。
"至多 k"
一个单调约束:若 [l,r] 满足,则其内部更小的窗口也一定满足。 这就是窗口所依赖的不变式。
"k 种不同"
内部状态变成多重集,但机制完全相同。
05 / 常见坑
收缩用
while,而不是 if。单次收缩往往无法恢复不变式。内层循环必须运行到窗口重新合法 — 否则你会把一个破碎的窗口带到下一步。
在错误的时刻记录答案。
应当在收缩之后窗口合法时再更新
best,而不是在收缩过程中。 中间的脏状态不是答案。窗口长度的边界差一。
闭区间下长度为
right − left + 1;半开区间下为 right − left。选定一种约定后,绝不混用。06 / 去 LeetCode 上练习
简单3
中等29
01Longest Substring Without Repeating Characters— LC 3→02Longest Substring with At Most Two Distinct Characters— LC 159→03Minimum Size Subarray Sum— LC 209→04Longest Substring with At Most K Distinct Characters— LC 340→05Longest Substring with At Least K Repeating Characters— LC 395→06Longest Repeating Character Replacement— LC 424→07Find All Anagrams in a String— LC 438→08Max Consecutive Ones II— LC 487→09Subarray Sum Equals K— LC 560→10Permutation in String— LC 567→11Fruit Into Baskets— LC 904→12Binary Subarrays With Sum— LC 930→13Subarray Sums Divisible by K— LC 974→14Max Consecutive Ones III— LC 1004→15Grumpy Bookstore Owner— LC 1052→16Get Equal Substrings Within Budget— LC 1208→17Replace the Substring for Balanced String— LC 1234→18Count Number of Nice Subarrays— LC 1248→19Maximum Number of Occurrences of a Substring— LC 1297→20Number of Substrings Containing All Three Characters— LC 1358→21Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→22Maximum Number of Vowels in a Substring of Given Length— LC 1456→23Longest Subarray of 1's After Deleting One Element— LC 1493→24Check If Array Pairs Are Divisible by k— LC 1497→25Maximize the Confusion of an Exam— LC 2024→26K Radius Subarray Averages— LC 2090→27Maximum Sum of Distinct Subarrays With Length K— LC 2461→28Take K of Each Character From Left and Right— LC 2516→29Maximum Sum of Almost Unique Subarray— LC 2841→
困难11
01Substring with Concatenation of All Words— LC 30→02Minimum Window Substring— LC 76→03Contains Duplicate III— LC 220→04Sliding Window Maximum— LC 239→05Sliding Window Median— LC 480→06Minimum Window Subsequence— LC 727→07Shortest Subarray with Sum at Least K— LC 862→08Subarrays with K Different Integers— LC 992→09Minimum Number of Operations to Make Array Continuous— LC 2009→10Maximum Number of Robots Within Budget— LC 2398→11Count Subarrays With Fixed Bounds— LC 2444→
— / 什么时候用哪个
对向
当数组已排序且答案是一对时使用。
两数之和 · 回文 · 容器
快 / 慢
用于原地修改或环的检测。
去重 · 链表环
滑动窗口
当条件围绕一段连续区间时使用。
最长/最短 · 至多 k