能否用前缀和求解「最多含k个奇数的子数组个数」问题？

问题解答 #

这个变体题完全可以通过前缀和求解，且能保持O(n)的时间复杂度，核心思路可基于你已有的前缀和逻辑，结合直接统计满足条件的前缀对数量实现。

核心思路

我们先定义prefix[i]为前i个元素中奇数的个数（prefix[0] = 0，对应空数组）。对于子数组nums[j..i-1]，其包含的奇数个数为prefix[i] - prefix[j]，要求该值 ≤k，等价于prefix[j] ≥ prefix[i] -k。

我们需要统计所有i（从1到数组长度）对应的j（从0到i-1）的数量之和，其中j满足prefix[j] ≥ prefix[i] -k。为了高效完成这个统计，我们可以维护两个数组：

• count[x]：记录前缀奇数个数为x的出现次数
• pre_sum[x]：记录count[0]到count[x]的累加和，用于快速计算区间内的count总和

实现代码

int atMostK(vector<int>& nums, int k) {
    if (k < 0) return 0;
    int n = nums.size();
    vector<int> count(n + 1, 0);
    vector<int> pre_sum(n + 1, 0);
    count[0] = 1;
    pre_sum[0] = 1;
    
    int current_odd = 0;
    int ans = 0;
    
    for (int num : nums) {
        // 更新当前前缀的奇数个数
        if (num % 2 != 0) {
            current_odd++;
            pre_sum[current_odd] = pre_sum[current_odd - 1] + count[current_odd];
        }
        
        // 计算满足条件的前缀数量：prefix[j] >= current_odd -k
        int lower = max(0, current_odd - k);
        if (current_odd == 0) {
            ans += pre_sum[0];
        } else {
            ans += pre_sum[current_odd] - (lower > 0 ? pre_sum[lower - 1] : 0);
        }
        
        // 更新计数数组与前缀和数组
        count[current_odd]++;
        if (current_odd == 0) {
            pre_sum[0] = count[0];
        } else {
            pre_sum[current_odd] = pre_sum[current_odd - 1] + count[current_odd];
        }
    }
    return ans;
}

适配你原有代码风格的简化版本

如果你想复用之前的prefixSum数组逻辑，可以维护一个前缀和数组快速计算区间和：

int atMostK(vector<int>& nums, int k) {
    if (k < 0) return 0;
    int total = 0;
    int ans = 0;
    vector<int> prefixSum{1};
    vector<int> sumPrefix{1}; // sumPrefix[i] = sum(prefixSum[0..i])
    
    for (int num : nums) {
        if (num % 2 != 0) {
            total++;
            prefixSum.push_back(1);
            sumPrefix.push_back(sumPrefix.back() + 1);
        } else {
            prefixSum.back()++;
            sumPrefix.back()++;
        }
        
        int lower = max(0, total - k);
        if (lower == 0) {
            ans += sumPrefix[total];
        } else {
            ans += sumPrefix[total] - sumPrefix[lower - 1];
        }
    }
    return ans;
}

这个版本中，prefixSum记录各前缀奇数个数对应的可选起始点数量，sumPrefix作为前缀和数组，让我们可以在O(1)时间内算出满足条件的起始点总数，最终得到最多包含k个奇数的子数组个数。

内容的提问来源于stack exchange，提问作者Linda