1248.Count Number of Nice Subarrays

Tags: Two Pointers Medium

Links: https://leetcode.com/problems/count-number-of-nice-subarrays/

---

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

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:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 50000
• 1 <= nums[i] <= 10^5
• 1 <= k <= nums.length

---

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        vector<int> oddNum;
        oddNum.push_back(-1);
        for (int i = 0; i < n; ++i) {
            if (nums[i] & 1) oddNum.push_back(i);
        }

        int len = oddNum.size() - 1;
        oddNum.push_back(n);
        int cnt = 0;
        for (int i = 1; i + k - 1 <= len; ++i) {
            cnt += (oddNum[i] - oddNum[i - 1]) * (oddNum[i + k] - oddNum[i + k - 1]);
        }

        return cnt;
    }
};

Runtime: 64 ms, faster than 98.53% of C++ online submissions for Count Number of Nice Subarrays.
Memory Usage: 18.8 MB, less than 100.00% of C++ online submissions for Count Number of Nice Subarrays.

用最后一个测试用例比较直观，

下标 0 1 2 3 4 5 6 7 8 9
数据 2 2 2 1 2 2 1 2 2 2
奇数的位置是3和6

考虑人工寻找完美子数组的方法，确定下标3和6之后，发现3之前的都是偶数，6之后的也都是偶数，那么在0-3和6-9这些位置都可以组成完美子数组，所以总数是$4\times 4 = 16$。所以问题归结为如何统计两个边界前后的所能放置的位置，和找到奇数的位置。

所以遍历一次数组，找到所有奇数的位置，用一个数组oddNum存储所有奇数的位置，于是可以利用的位置就是前后两个奇数位置的差值。考虑边界条件，比如下标为3的奇数前面没有奇数，怎么计算长度？下标为6的奇数后面没有奇数了，如何计算长度？从manacher算法借鉴思路，首尾加上-1和n即可。注意-1应该是最开始就加入到oddNum，如果放到最后再加，性能会变差，因为需要移动剩余的数字。用len代表实际奇数位置的长度。