力扣刷题笔记：滑动窗口法python模板写法（详细注释，广泛使用，秒杀滑窗题）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了力扣刷题笔记：滑动窗口法python模板写法（详细注释，广泛使用，秒杀滑窗题），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2164字，纯文字阅读大概需要4分钟。

内容图文

滑动窗口模板：

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

滑窗模板python代码：

def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想：

定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；

第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；

第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；

在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。

right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 [left, right] 不符合题意 。

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/
来源：力扣（LeetCode）https://leetcode-cn.com/problems/max-consecutive-ones-iii/

内容总结

以上是互联网集市为您收集整理的力扣刷题笔记：滑动窗口法python模板写法（详细注释，广泛使用，秒杀滑窗题）全部内容，希望文章能够帮你解决力扣刷题笔记：滑动窗口法python模板写法（详细注释，广泛使用，秒杀滑窗题）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端