滑动窗口
1.滑动窗口通用模板
1 | def findSubArray(nums): |
滑动窗口中用到了左右两个指针,它们移动的思路是:以右指针作为驱动,拖着左指针向前走。右指针每次只移动一步,而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移,探索未知的新区域;左指针是被迫移动,负责寻找满足题意的区间。
模板的整体思想是:
定义两个指针 left 和 right 分别指向区间的开头和结尾,注意是闭区间;定义 sums 用来统计该区间内的各个字符出现次数;
第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界;当 right 每次到了新位置,需要增加 right 指针的求和/计数;
第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置;当 left 每次移动到了新位置,需要减少 left 指针的求和/计数;
在第二重 while 循环之后,成功找到了一个符合题意的 [left, right] 区间,题目要求最大的区间长度,因此更新 res 为 max(res, 当前区间的长度) 。
right 指针每次向右移动一步,开始探索新的区间。
模板中的 sums 需要根据题目意思具体去修改,本题是求和题目因此把sums 定义成整数用于求和;如果是计数题目,就需要改成字典用于计数。当左右指针发生变化的时候,都需要更新 sums 。
2.固定滑动窗口
leetcode 643. 子数组最大平均数 I
1 | public static double findMaxAverage(int[] nums, int k) { |
leetcode 1052.爱生气的书店老板
1 | public static int maxSatisfied(int[] customers, int[] grumpy, int X) { |