Medium

题目描述

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数组中没有奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

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

解题思路

解题思路

这道题要求统计包含恰好 k 个奇数的连续子数组个数。我们可以从多个角度来解决：

方法一：前缀和 + 哈希表（推荐）

将每个奇数看作 1，偶数看作 0，问题转化为求和为 k 的子数组个数。使用前缀和思想，对于位置 i，我们需要找到有多少个位置 j (j < i) 使得 prefixSum[i] - prefixSum[j] = k，即 prefixSum[j] = prefixSum[i] - k。

用哈希表记录每个前缀和出现的次数，遍历数组时：

  1. 更新当前前缀和
  2. 查找 prefixSum - k 在哈希表中的出现次数，累加到结果
  3. 更新哈希表中当前前缀和的计数

方法二：滑动窗口

使用两个指针维护一个包含恰好 k 个奇数的窗口。关键在于当窗口内奇数个数等于 k 时，需要计算以当前右端点结尾的所有有效子数组个数。

方法三：奇数位置记录

记录所有奇数的位置，然后对于每 k 个连续的奇数，计算包含它们的子数组个数。

前缀和方法实现简洁，时间复杂度最优，是最推荐的解法。

代码实现

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;  // 初始化，前缀和为0出现1次
        
        int prefixSum = 0;
        int result = 0;
        
        for (int num : nums) {
            // 奇数计为1，偶数计为0
            prefixSum += num % 2;
            
            // 查找prefixSum - k是否存在
            if (prefixCount.find(prefixSum - k) != prefixCount.end()) {
                result += prefixCount[prefixSum - k];
            }
            
            // 更新当前前缀和的计数
            prefixCount[prefixSum]++;
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix_count = {0: 1}  # 初始化，前缀和为0出现1次
        prefix_sum = 0
        result = 0
        
        for num in nums:
            # 奇数计为1，偶数计为0
            prefix_sum += num % 2
            
            # 查找prefix_sum - k是否存在
            if prefix_sum - k in prefix_count:
                result += prefix_count[prefix_sum - k]
            
            # 更新当前前缀和的计数
            prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
        
        return result

public class Solution {
    public int NumberOfSubarrays(int[] nums, int k) {
        Dictionary<int, int> prefixCount = new Dictionary<int, int>();
        prefixCount[0] = 1;  // 初始化，前缀和为0出现1次
        
        int prefixSum = 0;
        int result = 0;
        
        foreach (int num in nums) {
            // 奇数计为1，偶数计为0
            prefixSum += num % 2;
            
            // 查找prefixSum - k是否存在
            if (prefixCount.ContainsKey(prefixSum - k)) {
                result += prefixCount[prefixSum - k];
            }
            
            // 更新当前前缀和的计数
            if (prefixCount.ContainsKey(prefixSum)) {
                prefixCount[prefixSum]++;
            } else {
                prefixCount[prefixSum] = 1;
            }
        }
        
        return result;
    }
}

var numberOfSubarrays = function(nums, k) {
    const prefixCount = new Map();
    prefixCount.set(0, 1);  // 初始化，前缀和为0出现1次
    
    let prefixSum = 0;
    let result = 0;
    
    for (const num of nums) {
        // 奇数计为1，偶数计为0
        prefixSum += num % 2;
        
        // 查找prefixSum - k是否存在
        if (prefixCount.has(prefixSum - k)) {
            result += prefixCount.get(prefixSum - k);
        }
        
        // 更新当前前缀和的计数
        prefixCount.set(prefixSum, (prefixCount.get(prefixSum) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
前缀和 + 哈希表O(n)O(n)
滑动窗口O(n)O(1)
奇数位置记录O(n)O(k)

推荐使用前缀和方法，代码简洁且容易理解。

相关题目