跳至主要內容

定长滑动窗口：解决子数组问题的利器 🎯

司徒2024年3月18日大约 4 分钟算法随笔滑动窗口双指针算法技巧LeetCode

定长滑动窗口：解决子数组问题的利器 🎯

引言

在算法题中，我们经常会遇到需要处理连续子数组或子串的问题。定长滑动窗口（Fixed-size Sliding Window）就是解决这类问题的利器之一。今天，让我们一起来探索这个优雅的算法技巧！ 🚀

什么是定长滑动窗口？ 🤔

定长滑动窗口是一种特殊的双指针技巧，它维护一个固定大小的窗口，通过移动窗口来解决问题。想象一下，就像你在看一列火车，每次只能看到固定数量的车厢，随着火车移动，你看到的内容也在变化。

适用场景 🎯

定长滑动窗口特别适合解决以下类型的问题：

  1. 求固定长度的子数组的最大值/最小值
  2. 求固定长度的子数组的和
  3. 判断是否存在固定长度的子数组满足特定条件
  4. 统计固定长度的子数组的个数

工作原理 ⚙️

让我们通过一个简单的例子来理解定长滑动窗口的工作原理：

假设我们要在一个长度为 n 的数组中，找到长度为 k 的子数组的最大和。滑动窗口的过程如下：

  1. 初始化窗口：计算第一个长度为 k 的子数组的和
  2. 滑动窗口：每次向右移动一位，同时：
    • 减去窗口最左边的元素
    • 加上窗口最右边的元素
  3. 更新结果：比较当前窗口的和与历史最大值

代码实现 💻

让我们看一个具体的例子，计算长度为 k 的子数组的最大和：

def maxSubArraySum(arr, k):
    # 数组长度小于k时直接返回
    if len(arr) < k:
        return None
    
    # 计算第一个窗口的和
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # 滑动窗口
    for i in range(k, len(arr)):
        # 减去最左边的元素，加上最右边的元素
        window_sum = window_sum - arr[i-k] + arr[i]
        # 更新最大值
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# 测试代码
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 3
print(f"长度为{k}的子数组的最大和是: {maxSubArraySum(arr, k)}")

实战练习 🎮

下面是一些使用定长滑动窗口解决的 LeetCode 题目，按照难度从简单到困难排序：

简单题

中等题

困难题

优化技巧 🚀

  1. 空间优化：如果只需要计算和，不需要存储窗口内的所有元素
  2. 提前返回：如果找到满足条件的解，可以立即返回
  3. 边界处理：注意处理数组长度小于窗口大小的情况
  4. 滑动优化：根据具体问题，可以优化滑动的步长

常见陷阱 ⚠️

  1. 忘记处理边界情况
  2. 窗口大小不固定
  3. 没有正确更新窗口状态
  4. 时间复杂度计算错误

结语 🎉

定长滑动窗口是一个简单但强大的算法技巧，掌握它可以帮助我们解决很多实际问题。记住，熟能生巧，多练习才能更好地掌握这个技巧！

💡 提示：在解决滑动窗口问题时，建议先在纸上画出窗口滑动的过程，这样可以帮助我们更好地理解问题。

🎯 练习建议：从简单的题目开始，逐步增加难度，这样可以帮助我们更好地掌握这个技巧。