当前位置：首页 > news >正文

LeetCode算法模板宝典：滑动窗口与双指针的终极解法

news 2026/7/18 10:00:39

LeetCode算法模板宝典：滑动窗口与双指针的终极解法

【免费下载链接】leetcodepython 数据结构与算法 leetcode 算法题与书籍刷算法全靠套路与总结！Crack LeetCode, not only how, but also why.项目地址: https://gitcode.com/gh_mirrors/leetcode82/leetcode

在LeetCode算法题中，滑动窗口与双指针技巧是解决数组、字符串类问题的黄金法则。本文将系统讲解这两种高效算法的核心模板、应用场景及实战技巧，帮助你快速掌握解题套路，轻松应对中等难度的算法挑战。

算法思维全景：从数据结构到解题策略

算法学习的关键在于建立完整的知识体系。下图展示了算法世界的核心构成，其中滑动窗口和双指针作为重要的解题技巧，广泛应用于数组、字符串和链表等数据结构的操作中：

为什么选择滑动窗口与双指针？

时间效率：将嵌套循环的O(n²)复杂度降至O(n)
空间效率：通常只需O(1)或O(k)的额外空间（k为窗口大小）
普适性：覆盖70%以上的字符串和数组中等难度题目

滑动窗口：动态区间的艺术

滑动窗口通过维护一个动态变化的区间（窗口）来解决子串/子数组问题，核心思想是右指针扩张、左指针收缩，动态调整窗口大小以满足条件。

标准模板解析

def sliding_window_template(s, p): counter = Counter(p) # 初始化目标状态 start, end = 0, 0 # 窗口边界 count = 0 # 条件计数器 res = 0 # 结果存储 while end < len(s): # 右指针扩张 counter[s[end]] += 1 if counter[s[end]] == 1: count += 1 end += 1 # 左指针收缩（满足条件时） while count == len(p): res = max(res, end - start) # 更新结果 counter[s[start]] -= 1 if counter[s[start]] == 0: count -= 1 start += 1 return res

核心应用场景

子串匹配问题：如「最小覆盖子串」「找到字符串中所有字母异位词」
区间最值问题：如「滑动窗口最大值」「长度最小的子数组」
去重计数问题：如「无重复字符的最长子串」

实战技巧

窗口条件设计：明确收缩窗口的触发条件（如达到目标字符数、出现重复元素）
状态维护：使用哈希表记录窗口内元素状态，避免重复计算
结果更新时机：求最大值在窗口收缩后更新，求最小值在窗口收缩前更新

双指针：双向协作的智慧

双指针通过两个指针的协同移动，将复杂问题简化为线性遍历。根据应用场景可分为快慢指针、左右指针和对撞指针等类型。

常见类型与模板

1. 左右指针（对撞指针）

def left_right_boundary(seq): left, right = 0, len(seq) - 1 while left < right: if seq[left] == target: # 左指针条件 left += 1 if seq[right] != target: # 右指针条件 right -= 1 # 处理逻辑 process(seq[left], seq[right])

典型应用：「两数之和」「反转字符串」「回文验证」

2. 快慢指针

def slow_fast_runner(seq): slow = 0 for fast in range(len(seq)): if seq[fast] != val: # 快指针筛选有效元素 seq[slow] = seq[fast] slow += 1 return slow # 返回有效长度

典型应用：「删除有序数组中的重复项」「环形链表检测」「寻找链表中点」

3. 滑动窗口双指针

def start_end_sliding_window(seq): start, end = 0, 0 while end < len(seq): end += 1 # 右指针扩张 while window_condition_not_met(start, end): start += 1 # 左指针收缩 update_result(start, end)

性能对比：双指针 vs 暴力法

从排序算法的性能对比可以看出，双指针技巧（如归并排序的指针操作）相比暴力法（如冒泡排序）有显著的效率提升，时间复杂度从O(n²)降至O(n log n)。

实战进阶：模板组合与变形

滑动窗口 + 双指针：滑动窗口本质是双指针的特殊形式

# 最长重复子数组（滑动窗口+动态规划） def findLength(A, B): m, n = len(A), len(B) max_len = 0 # 固定A，滑动B for i in range(m): length = 0 for j, k in zip(range(n), range(i, m)): if A[k] == B[j]: length += 1 max_len = max(max_len, length) else: length = 0 return max_len

常见误区与解决方案

边界处理：循环条件使用left <= right还是left < right？
- 对撞指针通常用left < right（避免重复处理）
- 滑动窗口用end < len(seq)控制右边界
状态更新：哈希表计数器的增减顺序
- 右指针先增后判断，左指针先判断后减
结果计算：窗口长度的计算方式
- 闭区间：end - start + 1
- 开区间：end - start