1248. 统计「优美子数组」

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。

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

//前缀和+ 记录哈希键 + 同余定理，时空都是On
func numberOfSubarrays(nums []int, k int) int {
    count := 0                  //1,定义出现频次，前缀和，和差值为=k的哈希v-k表
    preOddCount:= 0             // 1，做出前缀和，字典       
    hash_m := map[int]int{0: 1}        //这句不懂？   用于计算和刚好为k的情况
    for i := 0; i < len(nums); i++ {
        if nums[i] % 2 == 0 {           //判断遍历的命中的数的奇偶，偶数直接算人头；奇数数字+1，再算人头
            hash_m[preOddCount] += 1
        } else {
            preOddCount += 1
            hash_m[preOddCount] += 1
        }
        if preOddCount >= k {           //若奇数的数，超过k个，就移除哈希的计数键
            count += hash_m[preOddCount - k]
        } 
    } 
    return count
}

//排列组合法，时空也是On，小聪明
func numberOfSubarrays(nums []int, k int) int {
    odd := make([]int, len(nums)+1)
    oddNum, prefixLen := 0, 0
    ans := 0
    for i := 0; i <= len(nums); i++ {
        prefixLen += 1 //自己也要算进去
        if i == len(nums) || nums[i]%2 == 1 {
            odd[oddNum] = prefixLen
            if oddNum >= k {
                ans += odd[oddNum-k] * odd[oddNum]
            }
            oddNum += 1
            prefixLen = 0
        }
    }
    return ans
}

// 滑动窗口 一次遍历，时间On，空间O1
func numberOfSubarrays(nums []int, k int) int {
    left, right, oddCount, res := 0, 0, 0, 0

    for right < len(nums){
        if nums[right] & 1 == 1{
            oddCount++  // 奇数
        }
        right++
        if oddCount == k{           // right向右直到找到奇数或越界停下
            tmpRight := right       // 记下当前right位置
            for right < len(nums) && nums[right] & 1 == 0{
                right++
            }
            rightEvenCount := right - tmpRight

            leftEvenCount := 0          // left向左找到奇数或越界之后停下
            for nums[left] & 1 == 0{
                left++                  // left往右走，到第一个奇数时停下
                leftEvenCount++
            }

            // 此时left为第一个奇数的位置，left++就在左侧让出一个奇数
            res += (leftEvenCount+1) * (rightEvenCount+1)  
            left++
            oddCount--          // 左侧少了一个奇数，所以奇数的计数器要减一
        }
    }
    return res
}