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
- Replace each element by its parity (
x % 2). The problem then becomes counting subarrays with sum exactlyk. - Apply the same "at most k minus at most k-1" decomposition as in Binary Subarrays With Sum.
atMost(g)uses a sliding window whose parity sum stays at mostg.- 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 < 0guard: needed whenk = 0(although the constraints start atk >= 1, the general form should handle it). - Using
x % 2 == 1and summing booleans: works in Python, butx & 1is 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner