⚡Flashcard Drill➔
NeetCode #244LC-1248MediumSliding Window
← Back to All Problems

#244 · #1248 · Count Number of Nice Subarrays(统计「优美子数组」数目)

📌 Problem Statement & Constraints

Given an array of integers nums and an integer k, return the number of nice subarrays: contiguous subarrays with exactly k odd numbers. Constraints: 1 <= nums.length <= 5 * 10^4, 1 <= nums[i] <= 10^5, 1 <= k <= nums.length.

💡 Core Algorithmic Approaches

  1. Replace each element by its parity (x % 2). The problem then becomes counting subarrays with sum exactly k.
  2. Apply the same "at most k minus at most k-1" decomposition as in Binary Subarrays With Sum.
  3. atMost(g) uses a sliding window whose parity sum stays at most g.
  4. All values are non-negative, so the window is valid.

💻 Benchmark Python3 Implementation

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(g: int) -> int:
            if g < 0:
                return 0
            l = 0
            odd = 0
            res = 0
            for r, x in enumerate(nums):
                odd += x & 1           # parity
                while odd > g:
                    odd -= nums[l] & 1
                    l += 1
                res += r - l + 1
            return res

        return atMost(k) - atMost(k - 1)


# Prefix-sum variant: count of prefixes with each odd-count, then sum products
class Solution2:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        cnt[0] = 1
        cur = 0
        res = 0
        for x in nums:
            cur += x & 1
            res += cnt[cur - k]        # earlier prefixes with k fewer odds
            cnt[cur] += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two passes for the window version, one pass for the prefix-sum version.
💾 Space Complexity
O(1) for the window version; O(n) for the prefix-sum version.

⚠️ Interview Pitfalls & Follow-ups

  • Counting subarrays with at least k odds: the problem requires exactly k.
  • Forgetting the g < 0 guard: needed when k = 0 (although the constraints start at k >= 1, the general form should handle it).
  • Using x % 2 == 1 and summing booleans: works in Python, but x & 1 is more direct and avoids the modulo.
  • Confusing this with the maximum-length problem: here the count of subarrays is required, not the longest one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems