GuilinDev

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

    1 <= nums.length <= 50000

  • 1

    1 <= nums[i] <= 10^5

  • 1

    1 <= k <= nums.length

分析

1) 滑动窗口

  • 刚开始时，不断移动右指针来扩大滑动窗口，使其包含k个奇数；
  • 当滑动窗口已经包含k个奇数时，做如下操作：
    • 统计第 1 个奇数左边的偶数个数 leftEvenCount。 这 leftEvenCount 个偶数都可以作为优美子数组的起点，因此起点的选择有 leftEvenCount + 1 种（可以一个偶数都不取，因此别忘了 +1 ）。
    • 统计第 k 个奇数右边的偶数个数 rightEvenCount 。 这 rightEvenCount 个偶数都可以作为优美子数组的终点，因此终点的选择有 rightEvenCount + 1 种（可以一个偶数都不取，因此别忘了 +1 ）。
    • 因此「优美子数组」左右起点的选择组合数为 
      1

      (leftEvenCnt + 1) * (rightEvenCnt + 1)
      。

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

2) 前缀和

  • 计算前缀和数组 
    1

    arr
    ：遍历原数组，每遍历一个元素，计算当前的前缀和（这里到当前元素为止，数组中有多少个奇数）；
  • 对上述前缀和数组，可以双重循环统计 
    1

    arr[j] - arr[i] == k
    的个数，这样做是 O(N^2) 的（这样做会超时）。
  • 优化：可以像「1. 2Sum」那样使用 HashMap 优化到 O(N)，其中键是「前缀和」，值是「前缀和的个数」也可以如下面代码一样，使用的是 int[] prefixCount 数组，下标是「前缀和」，值是「前缀和的个数」，因此可以遍历原数组，每遍历到一个元素，计算当前的前缀和 sum，就在 result 中累加上前缀和为 sum - k 的个数。

时间复杂度 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;
    }
}
This site is open source. Improve this page.