[leetcode]No. 1248 统计「优美子数组」

[liangbus]

1248. 统计「优美子数组」
给你一个整数数组 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

开始拿到这题，首先想到的也是用滑动窗口，思路如下：

首先定义两个指针，初始值都指向数组起始位置，声明一个临时数组，用于存放奇数值；
开始遍历，移动右指针，遇到奇数，则加入临时数组中，不断移动右指针，直到临时数组长度达到 k 值，开始计数符合条件的子数组 count 值，直到遇到下一个奇数，或者右指针到达数组末端，然后清空临时数组，左指针右移，右指针回到与左指针相同的位置，本轮循环结束
新一轮循环开始，如此重复

代码如下，这个方法是可行，在 leetcode 上面能跑完60%以上的用例，只是后面数据长度过长导致超时了
我看完题解之后，感觉我的不太像滑动窗口，应该只是暴力的变形

var numberOfSubarrays = function(nums, k) {
    const len = nums.length
    if(!len || len < k) return 0
    let left = 0, right = 0
    let count = 0
    let tmp = []
    while(left < len) {
        if(isOdd(nums[right])) {
            tmp.push(nums[right])
        }
        right++
        if(tmp.length === k) count++
        if(right === len || tmp.length > k) {
            tmp = []
            left++
            right = left
        }
    }
    return count
};

function isOdd(n) {
    return n % 2 !== 0
}

然后参考题解，发现甜姨的方法真的很巧妙（就是那种，一看就很清晰，但自己就想不到的）

思路：

滑动窗口

前面跟我的类似定义好双指针

var numberOfSubarrays = function(nums, k) {
    const len = nums.length
    if(!len || len < k) return 0
    let left = 0, right = 0
    let count = 0
    let tmp = []
    while(right < len) {
        if(isOdd(nums[right])) {
            tmp.push(nums[right])
        }
        right++
        if(tmp.length === k) {
            subEndIndex = right
            let leftEvenCount = 0
            let rightEvenCount = 0
            while(!isOdd(nums[left])) {
                leftEvenCount++
                left++
            }
            while(!isOdd(nums[right])) {
                rightEvenCount++
                right++
            }
            count += (leftEvenCount + 1) * (rightEvenCount + 1)
            tmp.splice(0, 1) // 删除第一个奇数
            left++ // 当前指向第一个奇数，右移一位
        }
    }
    return count
};
// 奇数
function isOdd(n) {
    return n % 2 !== 0
}