LeetCode学习笔记——统计优美子数组（SlidingWindow)

前言已经在LeetCode刷了两百多道题了带来的感受肯定跟一个多月前是不一样的但做题能力实际上没增加多少。现在如果看到题目读懂题了

前言

已经在LeetCode刷了两百多道题了带来的感受肯定跟一个多月前是不一样的但做题能力实际上没增加多少。现在如果看到题目读懂题了基本都能判断出属于哪种类型的题然后应该用什么方法做这一点我觉得也是一种进步吧。毕竟来LeetCode的初心并不是为了准备面试而是为了培养自己的思维然后熟悉各式各样的算法结构和应用这点我觉得自己做到了。

今天记录的是一道打卡题一开始看到这道题马上就能想到用滑动窗口来做我本来是想用基本套路解决的发现没那么简单需要转换一下思想。

统计优美子数组

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1

输入nums [1,1,2,1,1], k 3输出2解释包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2

输入nums [2,4,6], k 1输出0解释数列中不包含任何奇数所以不存在优美子数组。

示例 3

输入nums [2,2,2,1,2,2,1,2,2,2], k 2输出16

解题思路

对于nums [1,1,2,1,1]k 3我们一下子就可以判断出两个子数组是 [1,1,2,1] 和 [1,2,1,1] 但对于 [2,2,2,1,2,2,1,2,2,2] k 2 这么长的数组来说一下子看上去可不能很快得出答案。

一般的我们解决滑动窗口问题的套路是搞两个指针一开始都指向首位然后右指针开始移动扩大窗口然后再左指针缩小窗口。

但这道题不是这道题应该先要确定窗口的大小然后向两边扩展那窗口的大小怎么确定呢

对于 [2,2,2,1,2,2,1,2,2,2] k 2 我们知道符合条件的最小长度的子数组是 [1,2,2,1]往左边扩展可以扩展三位还可以不扩展所以一共是4种情况右边扩展同样是四种情况所以最后的总的子数组是 4 * 4 16。

但实际上我们还是确定不了窗口的边界我们做题毕竟不是看出来的还是要深究其中的原理我们可以这样子做

先取出数组中所有奇数值的下标

我们另取一个更具一般性的例子进行说明 nums [2, 1, 5, 6, 7, 3, 4, 9, 8], k 3,这个例子想一眼看出来还真的不那么容易像我们上面所说取出所有奇数值的下标

取出后是这样子的橙色部分储存奇数值下标你可能发现了index数组的首尾和后面分别是 -1 和 数组的长度你先不管这里后面会进行说明

当我们根据k进行划定窗口的时候首先是在 index 里面划定边界比如

此时窗口边界就确定了左右边界对应的下标是 [1, 4]那在数组 nums 中对应的就如黄色区域

黄色区域就代表包括 1,5,7三个奇数在内的最小长度的子数组也叫做最小窗口

此时该窗口是可以扩展的但扩展是有条件限制的并不能无限扩展当扩展到数组边界时或者将要把第四个奇数纳入到窗口中就应该停下来所以对于该窗口可以往左边扩展将 2 纳入但右边不能再继续扩展像这样

那么包括 1,5,7的子数组的数量应该是多少呢

应该为 2 * 1 2一共是两个往左边有两种选择扩展1位或者不扩展右边就只有选择不扩展一种情况。

还记得index数组首位的 -1 吗它的作用就是代表着不扩展这种情况奇数 1 对应的下标 1 代表着是左边还有 1 个位置可以扩展所以计算左边可以计算 index[1] - index[0] 2窗口最右边的奇数是 7对应下标是4处在index[3]往右边直到遇到第四个奇数都是可以继续扩展的那第四个奇数的对应下标减去4就是窗口的数量如 index[4] - index[3] 1就是右边可扩展的情况

好刚刚我们讨论的是包括1,5,7的情况但我们奇数还没完此时 index 数组中的窗口要继续移动

接着要讨论包括 5,7,3的情况像这样

包括5,7,3的情况按照以上的步骤进行讨论就行

但7,3,9处在边界就特殊一点

左边同理扩展到不能扩展为止往左边会扩展到奇数 5 处停下所以左边的子数组数量是 4 - 2 2而右边会遇到数组的边界奇数 9 对应的数组下标是 7数组长度减去 7即 9 - 7 2当然我们都是在index 数组中进行操作所以在index数组中对应的就是 index[6] - index[5] 9 - 7 2所以index数组中最后面一个元素是数组的长度的原因就在这。

代码

class Solution {public int numberOfSubarrays(int[] nums, int k) {//创建储存奇数下标的数组int []index new int[nums.length 2];//j作为移动的指针因为index数组的首位等于 -1所以从 1 开始int j 1;//录入奇数在nums中的下标for(int i 0; i < nums.length; i) {if(nums[i] % 2 ! 0) {index[j] i;}}//数组的首位为 -1后面不是末尾为数组长度index[0] -1;index[j] nums.length;int res 0;//i 从index 下标 1 开始j 是当前 index 里面存有值的长度 i k代表窗口for(int i 1; i k < j; i) {//计算当前包括k个奇数的子数组的数量res (index[i] - index[i - 1]) * (index[i k] - index[i k - 1]);}return res;}}

​

---

整理于2020.4.21