LeetCode 高频题解：滑动窗口与双指针的通用解题框架

LeetCode 高频题解：滑动窗口与双指针的通用解题框架

一、滑动窗口的直觉与误区：不是所有连续子数组都适用

滑动窗口是 LeetCode 高频考点，但很多初学者的理解停留在"左右指针移动"的表面，遇到变形题就无从下手。核心误区有两个：第一，认为滑动窗口只适用于"连续子数组"问题，实际上只要满足"窗口内状态可增量更新"的条件，非连续场景也能用；第二，不知道何时用定长窗口、何时用变长窗口，导致框架选错。

滑动窗口的本质是：用 O(1) 或 O(log n) 的代价维护窗口内的状态，避免对每个子数组重新计算。关键判断标准是"窗口收缩时状态能否快速更新"——如果每次收缩都需要 O(n) 重建状态，滑动窗口就不比暴力解法更优。

二、滑动窗口的分类与框架

graph TB SW[滑动窗口] --> FIXED[定长窗口 大小固定] SW --> VAR[变长窗口 大小可变] VAR --> MIN[最小窗口 满足条件的最短] VAR --> MAX[最大窗口 满足条件的最长] FIXED --> AVG[滑动平均/最大值] FIXED --> FREQ[频率统计] MIN --> FRAME1[框架：右扩左缩 找最短] MAX --> FRAME2[框架：右扩左缩 找最长]

三、通用解题框架与经典题型

from collections import defaultdict, Counter from typing import List # ========== 框架 1：变长窗口 — 最小覆盖子串 ========== # LeetCode 76. Minimum Window Substring def min_window(s: str, t: str) -> str: """最小覆盖子串：找 s 中包含 t 所有字符的最短子串""" if not s or not t or len(s) < len(t): return "" need = Counter(t) # 需要的字符频率 window = defaultdict(int) # 窗口内的字符频率 valid = 0 # 满足要求的字符数 left = 0 min_len = float("inf") result = "" for right, ch in enumerate(s): # 右扩：将字符加入窗口 window[ch] += 1 if ch in need and window[ch] == need[ch]: valid += 1 # 左缩：当窗口满足条件时，尝试收缩 while valid == len(need): # 更新最短结果 if right - left + 1 < min_len: min_len = right - left + 1 result = s[left:right + 1] # 移除左端字符 left_ch = s[left] if left_ch in need and window[left_ch] == need[left_ch]: valid -= 1 window[left_ch] -= 1 left += 1 return result # ========== 框架 2：变长窗口 — 最长无重复子串 ========== # LeetCode 3. Longest Substring Without Repeating Characters def length_of_longest_substring(s: str) -> int: """最长无重复子串""" window = set() left = 0 max_len = 0 for right, ch in enumerate(s): # 左缩：直到窗口内无重复 while ch in window: window.remove(s[left]) left += 1 window.add(ch) max_len = max(max_len, right - left + 1) return max_len # ========== 框架 3：定长窗口 — 滑动最大值 ========== # LeetCode 239. Sliding Window Maximum from collections import deque def max_sliding_window(nums: List[int], k: int) -> List[int]: """定长滑动窗口最大值：单调队列 O(n)""" dq = deque() # 存储索引，保持对应值单调递减 result = [] for i, num in enumerate(nums): # 移除超出窗口的元素 while dq and dq[0] <= i - k: dq.popleft() # 移除比当前元素小的（它们不可能成为最大值） while dq and nums[dq[-1]] < num: dq.pop() dq.append(i) # 窗口形成后，队首就是最大值 if i >= k - 1: result.append(nums[dq[0]]) return result # ========== 框架 4：双指针 — 对撞指针 ========== # LeetCode 11. Container With Most Water def max_area(height: List[int]) -> int: """盛最多水的容器：对撞指针，每次移动较矮的指针""" left, right = 0, len(height) - 1 max_water = 0 while left < right: width = right - left h = min(height[left], height[right]) max_water = max(max_water, width * h) # 移动较矮的指针：只有换更高的柱子才可能增加面积 if height[left] < height[right]: left += 1 else: right -= 1 return max_water # ========== 框架 5：双指针 — 快慢指针 ========== # LeetCode 141/142. Linked List Cycle class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def detect_cycle(head: ListNode) -> ListNode: """检测链表环的入口：快慢指针 + 数学推导""" slow = fast = head # 第一阶段：快慢指针相遇 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: return None # 无环 # 第二阶段：一个指针从头部出发，与慢指针相遇即为环入口 # 数学证明：a = (n-1)(b+c) + c，其中 a 为头到入口，b 为入口到相遇，c 为相遇到入口 ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr

四、滑动窗口与双指针的 Trade-offs 分析

窗口状态维护的复杂度：字符频率统计用 Counter 即可，但如果窗口状态是"窗口内元素之和"或"窗口内最大值"，需要不同的数据结构。求和用前缀和 O(1)，求最大值用单调队列 O(1) 均摊，求中位数需要两个堆 O(log n)。

定长 vs 变长的选择：题目明确窗口大小用定长，否则用变长。变长窗口的难点在于"何时收缩"——需要明确定义"窗口满足条件"的判断标准。如果条件难以增量判断（如"窗口内元素互质"），滑动窗口可能不适用。

双指针的适用范围：对撞指针要求数组有序或具有单调性，快慢指针适用于链表和数组去重。双指针不能替代所有 O(n²) 枚举——如果问题不满足单调性，双指针无法保证正确性。

边界条件的处理：空输入、单元素、全相同元素是常见的边界陷阱。建议每个框架都包含空输入检查，并在窗口初始化时正确处理第一个元素。

五、总结

滑动窗口和双指针是 LeetCode 高频考点，核心是"用增量更新替代全量重算"。变长窗口分"最小覆盖"和"最长无重复"两种框架，定长窗口配合单调队列处理最值问题。双指针分对撞指针和快慢指针两类，分别适用于有序数组去重和链表环检测。掌握框架后，关键训练点是"窗口状态维护"的数据结构选择和"收缩条件"的精确定义。