Lc1248

05 August 2008

1248 Count Number of Nice Subarrays

原题

Given an array of integers 
1

nums
and an integer 
1

k
. A __subarray is called nice if there are 
1

k
odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

1
2
3

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

1
2
3

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:

1
2

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

Constraints:

分析

1) 滑动窗口

时间复杂度 O(N)，空间复杂度 O(1)

2) 前缀和

时间复杂度 O(N)，空间复杂度 O(N)

代码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int left = 0, right = 0, oddCount = 0, result = 0;
        while (right < nums.length) {
            // 右指针先走，每遇到一个奇数则 oddCount++。
            if ((nums[right++] & 1) == 1) {
                oddCount++;
            }

            //  若当前滑动窗口 [left, right) 中有 k 个奇数了，进入此分支统计当前滑动窗口中的优美子数组个数。
            if (oddCount == k) {
                // 先将滑动窗口的右边界向右拓展，直到遇到下一个奇数（或出界）
                // rightEvenCount 即为第 k 个奇数右边的偶数的个数
                int temp = right;
                while (right < nums.length && (nums[right] & 1) == 0) {// 偶数就继续右移
                    right++;
                }
                int rightEvenCount = right - temp;
                // leftEvenCount 即为第 1 个奇数左边的偶数的个数
                int leftEvenCount = 0;
                while ((nums[left] & 1) == 0) { // 偶数
                    leftEvenCount++;
                    left++;
                }
                // 第 1 个奇数左边的 leftEvenCount 个偶数都可以作为优美子数组的起点
                // (因为第1个奇数左边可以1个偶数都不取，所以起点的选择有 leftEvenCount + 1 种）
                // 第 k 个奇数右边的 rightEvenCnt 个偶数都可以作为优美子数组的终点
                // (因为第k个奇数右边可以1个偶数都不取，所以终点的选择有 rightEvenCount + 1 种）
                // 所以该滑动窗口中，优美子数组左右起点的选择组合数为 (leftEvenCount + 1) * (rightEvenCount + 1)
                result += (leftEvenCount + 1) * (rightEvenCount + 1);

                // 此时 left 指向的是第 1 个奇数，因为该区间已经统计完了，因此 left 右移一位，oddCount--
                left++;
                oddCount--;
            }

        }

        return result;
    }
}

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // 数组 prefixCount 的下标是前缀和（即当前奇数的个数），值是前缀和的个数。
        int[] prefixCount = new int[nums.length + 1];
        prefixCount[0] = 1;
        // 遍历原数组，计算当前的前缀和，统计到 prefixCount 数组中，
        // 并且在 result 中累加上与当前前缀和差值为 k 的前缀和的个数。
        int result = 0, sum = 0;
        for (int num: nums) {
            sum += num & 1;
            prefixCount[sum]++;
            if (sum >= k) {
                result += prefixCount[sum - k];
            }       
        }
        return result;
    }
}