前言
已经在LeetCode刷了两百多道题了,带来的感受肯定跟一个多月前是不一样的,但做题能力实际上没增加多少。现在如果看到题目,读懂题了基本都能判断出属于哪种类型的题,然后应该用什么方法做,这一点我觉得也是一种进步吧。毕竟来LeetCode的初心并不是为了准备面试,而是为了培养自己的思维,然后熟悉各式各样的算法结构和应用,这点我觉得自己做到了。
今天记录的是一道打卡题,一开始看到这道题,马上就能想到用滑动窗口来做,我本来是想用基本套路解决的,发现没那么简单,需要转换一下思想。
统计优美子数组
给你一个整数数组 nums
和一个整数 k
。
如果某个 连续 子数组中恰好有 k
个奇数数字,我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1:
1 | 输入:nums = [1,1,2,1,1], k = 3 |
示例 2:
1 | 输入:nums = [2,4,6], k = 1 |
示例 3:
1 | 输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2 |
解题思路
对于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数组中最后面一个元素是数组的长度的原因就在这。
代码
1 | class Solution { |
整理于2020.4.21