滑动窗口算法最简单的教程

技术2026-06-13 2

1 举个栗子

给定一个字符串，找到包含的不同字符个数不超过K的最长的连续子串

同样先来几个例子，以便准确地理解问题。

例子1：

输入: String="araaci", K=2

输出: 4

解释: 包含不同字符个数不超过2的最长的连续子串是 "araa"

例子2：

输入: String="araaci", K=1

输出: 2

解释: 包含不同字符个数不超过1的最长的连续子串是 "aa"

例子3：

输入: String="cbbebi", K=3

输出: 5

解释: 包含不同字符个数不超过3的最长的连续子串是 "cbbeb" 或者 "bbebi"

2 思路分析

因为字符串本质就是一个字符数组，所以本题实际上也是求子数组。只不过挑选的标准和前道题不同而已。

前道题是求最短，本题是求最长。

前道题是子数组元素的和不小于K，本道题是子数组元素（即字符）的种类数不超过K。明白了这两点不同，就清楚如何修改前道题的代码，来完成这道题的求解。

首先，还是从数组开头累积出一个最长的符合条件的子字符串，作为我们的窗口。其次，当滑动窗口后，尽可能避免收缩窗口，除非新窗口中包含的字符种类超过了限制。最后，我们需要实时记录窗口中包含的不同字符的个数，以便判断窗口是否符合K个不同字符的要求，这里，我们可以选择HashMap。

3 代码实现

def longest_substring_with_k_distinct(str1, k): window_start = 0 max_length = 0 char_frequency = {} # 在下面的循环中，我们将尽可能扩展 [window_start, window_end] 的范围 for window_end in range(len(str1)): right_char = str1[window_end] if right_char not in char_frequency: char_frequency[right_char] = 0 char_frequency[right_char] += 1 # 收缩滑动窗口, 直到char_frequency中的key的数目不超过K while len(char_frequency) > k: left_char = str1[window_start] char_frequency[left_char] -= 1 if char_frequency[left_char] == 0: del char_frequency[left_char] window_start += 1 # 收缩窗口 # 记录下当前最长的窗口长度 max_length = max(max_length, window_end-window_start + 1) return max_length

4 思考总结

如果大家看了前道题和本题，应该会有个感觉，滑动窗口算法，其实就是将原来的暴力算法进行了优化而已。主要的优化点其实有两个：

不去计算已经计算过的

不去计算根据条件确定不用计算的

第一点，就是滑动前后窗口重叠部分的数字的和，第二点，就是本题和前道题中窗口每滑动一步，直接从窗口左端进行收缩，实际上就是已经确定，窗口左端再往左的部分是不用考虑的。

如果大家有机器学习的知识，滑动窗口算法很像是对暴力算法的一个剪枝算法。

再深一步讲，所谓的动态规划，其实也是对暴力算法的一个优化，也就是不去计算已经算过的或者不用计算的部分。

大家在学习一个新的算法技巧时，可以采用这个学习的思路，即先用暴力算法进行实现，然后思考新的算法技巧是在哪部分进行了优化，这样就更容易理解算法技巧的本质。

如果理解了本文，那么leetcode上这道 https://leetcode.com/problems/fruit-into-baskets/ medium的题，对你就不在话下了。