滑动窗口

找出s中刚好包含t中所有字符串的子字符串,t中的字符串长度都相等,为wordLen,t中有wordNum个字符串。[1]首先构建t中字符串的计数器,然后以0到wordLen-1开头,从头到尾走wordLen的跳数,在跳动的滑动窗口内部讨论可能性,以及维持滑动窗口的边界。如果这一跳遇到的字符串没有在t中出现,更新滑动窗口的左边界到该一跳末尾,滑动窗口的块大小计数恢复为0,滑动窗口内部的计数器清空,因为从原先的left到现在这一跳的滑动窗口无法满足题目条件,有杂质;否则,更新目前滑动窗口内部块的数量和计数器,当滑动窗口内部的计数器和t的计数器匹配且块数量==wordNum,则找到了一个目标子字符串

找出nums乘积小于k的子数组个数。[2]
方法一:滑动窗口。统计以某一元素为结尾的乘积小于k的子数组个数,计算以某一元素为结尾的成绩小于k的最长子数组长度,计算子区间的乘积,维护滑动窗口中的元素积小于k。
方法二:前缀和,使用log函数变相乘运算为相加运算,注意log函数的结果是double,使用upper_bound在logPrefix数组中找logPrefix[i]-log(k)+1e-10的上界的索引,这样找到和小于log(k)的子区间,即乘积小于k的子数组。

nums中三个无重叠长度为k的最大和的子数组起始索引。[3]
方法一:滑动窗口。以第三个子数组的起始坐标i=2*k遍历找最大和,第一个子数组的起始坐标为i-k*2,第二个子数组的起始坐标为i-k,累计滑动窗口和;当i>=3*k-1时,即第一个靠左的三个长度为k的无重叠子数组形成,根据滑动窗口的和更新最大和和区域的起始坐标,三个滑动窗口一起向右走一步,再更新状态。
方法二:动态规划。dp[i][j]表示到索引j位置处前i个互不重叠长度为k的子数组的最大和,面对元素[j]时,可以选择它参与计算最大和,dp[i-1][j-k]+prefix[j]-prefix[j-k],也可以不选择它参与计算最大和,dp[i][j-1],取两者中的最大值,dp[2][n-1]即为最大和,记录计算最大和的转移路径(map[第i个子数组和]=子数组的起始索引,dp[2][i]的最大值是从dp[1][.]转移过来的,不断往前查找),给出答案。注意,计算dp[0][i]时i的取值范围为k-1<=i<n-2*k

包含m个1的01字符串,让k个1在一块的最小交换次数,一次交换指相邻元素的一次互换。[4],统计m个1之间的m-1个连续0的区间的0的个数,窗口涵盖k-1个连续0的区间,两个连续1之间的连续0区间中0的个数是0,则k-1个连续0区间移到k个1的外端的最小移动次数表示最少交换次数,连续0区间离k个1的两端哪端近往哪端移,算出次数,然后窗口开始移动,考虑k-1个连续0区间,后一次相比前一次的移动,次数变化:k-1个连续0区间,前半部分各减少一次(前半部分的和),后半部分各增加一次(后半部分的和),这部分比较负责,后半部分的区间和根据k的奇偶有不同的算法(最中间的区间在滑动后离1的两端的距离是否变化),区间和用前缀和表示。解法参考【多图】新手教程,一步步带你写,把Hard分解成Easy

参考链接:[1].30. 串联所有单词的子串
[2].713. 乘积小于 K 的子数组
[3].689. 三个无重叠子数组的最大和
[4].1703. 得到连续 K 个 1 的最少相邻交换次数

创建于2022.5.23/16.40,修改于2022.8.9/18.12