1248.统计优美子数组 (Medium)*

题目描述*

标签*

滑动窗口；前缀和；

思路 & 代码*

注意是恰有 k 个奇数，不是全是奇数。。。

滑动窗口，向右扩充直到窗口包含 k 个奇数，然后计算该窗口可以提供的子数组个数，统计第一个奇数左侧的偶数个数，这些偶数都可以去掉，形成一个新的子数组，同时还有第 k 个奇数右侧的偶数，也是这样。所以这段窗口可以提供的子数组数为 (leftEvevCnt + 1) * (rightEvenCnt + 1)。这样计算完成后右移左指针直到奇数个数为 k - 1，然后再向右扩充，直到结尾。

我们令奇数为 1，偶数为 0，那这个题就转换成了和为 k 的子数组个数。构造前缀和数组，然后统计 arr[i] - arr[j] = k 的个数，双重循环的时间复杂度为 $O(n^2)$ ，优化可以参考两数之和，每遍历到一个前缀和 sum，累加 sum - k 的个数。

滑动窗口前缀和

class Solution {
public:
    int numberOfSubarrays(vector<int> nums, int k) {
        int l = 0, r = 0, cnt = 0, res = 0;
        int len = nums.size();
        while(r < len) {
            if(nums[r++] & 1) {
                cnt++;
            }
            if(cnt == k) {
                int tmp = r;
                while(r < len && (nums[r] & 1) == 0) {
                    r++;
                }
                int rightEvenCnt = r - tmp;
                int leftEvenCnt = 0;
                while((nums[l] & 1) == 0) {
                    l++;
                    leftEvenCnt++;
                }
                res += (leftEvenCnt + 1) * (rightEvenCnt + 1);
                l++;
                cnt--;
            }
        }
        return res;
    }
};

class Solution {
public:
    int numberOfSubarrays(vector<int> nums, int k) {
        int len = nums.size();
        vector<int> prefixCnt(len + 1, 0);
        prefix[0] = 1;
        int sum = 0;
        int res = 0;
        for(auto& num : nums) {
            sum += num & 1;
            prefixCnt[sum]++;
            if(sum >= k) {
                res += prefixCnt[sum - k];
            }
        }
        return res;
    }
};

最后更新: July 23, 2022