【LeetCode算法成长之路】滑动窗口算法总结与经典题目分析

滑动窗口算法是一种用于处理字符串或数组中子串问题的高效方法。它通过维护一个窗口，在遍历字符串或数组的过程中，不断更新窗口大小，从而找出满足条件的子串或子序列。

在LeetCode上，滑动窗口算法常见于以下问题类型：

1. 子串问题：找出字符串中最长/最短的子串满足某种条件。
2. 字符统计：计算字符串中字符出现的次数。
3. 字母异位词：判断两个字符串是否由相同的字母构成，可以考虑使用滑动窗口。

以下是一些使用滑动窗口解决的经典问题：

• 无重复字符的最长子串
• 滑动窗口最大值
• 最小滑动窗口范围
• 滑动窗口中的最大值

解决这些问题通常需要设置两个指针，一个代表窗口的开始，另一个代表窗口的结束，根据需要更新窗口的大小或移动窗口。

以下是无重复字符的最长子串的示例代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 使用哈希集合记录字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为-1表示还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断扩大窗口直到出现重复字符
                occ.add(s[rk + 1])
                rk += 1
            # 更新最长无重复子串的长度
            ans = max(ans, rk - i + 1)
        return ans

滑动窗口算法是一种非常实用的技巧，可以解决许多字符串和数组问题。理解和熟练运用该算法对于高效解决编程问题至关重要。