How do I approach solving the 'Count Number of Nice Subarrays' problem?

Start by transforming the odd numbers to 1 and the even numbers to 0, then use prefix sums and a hash map to efficiently count subarrays with exactly k odd numbers.

Can I solve this problem using brute force?

Brute force solutions are too slow for large inputs, so it's crucial to use a more efficient approach like prefix sums and hash map lookups to get an O(n) solution.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the input array, because we only traverse the array once and perform constant-time operations for each element.

What other variations of this problem should I practice?

You should practice problems that involve counting subarrays with certain properties, such as subarrays with at most k odd numbers or subarrays with k even numbers.

Why does using a hash map make the solution efficient?

The hash map allows you to store and quickly look up prefix sums, enabling you to count subarrays that sum to exactly k in constant time for each element in the array.

#1248

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计「优美子数组」

给你一个整数数组 nums 和一个整数 k 。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。示例 1：输入： nums = [1,1,2,1,1], k = 3 输出： 2 解释：包含 3 个奇数的子数组是 […

数组哈希表数学滑动窗口前缀和

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：前缀和 + 数组或哈希表

题目求子数组中恰好有 $k$ 个奇数的子数组个数，我们可以求出每个前缀数组中奇数的个数 $t$ ，记录在数组或哈希表 $cnt$ 中。对于每个前缀数组，我们只需要求出前缀数组中奇数个数为 $t-k$ 的前缀数组个数，即为以当前前缀数组结尾的子数组个数。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = t = 0
        for v in nums:
            t += v & 1
            ans += cnt[t - k]
            cnt[t] += 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of prefix sums and hash map usage to solve the problem efficiently.
question_mark
Candidates should be able to explain how transforming the problem with binary values simplifies finding subarrays with k odd numbers.
question_mark
The candidate may struggle if they attempt brute force solutions without recognizing the need for optimization.

warning

常见陷阱

外企场景

error
Not transforming even numbers to zero and odd numbers to one, which can lead to an incorrect approach.
error
Attempting a brute-force solution that checks every subarray, which would be too slow for large inputs.
error
Not updating the hash map properly, which can lead to missing some valid subarrays or counting duplicates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count subarrays with at most k odd numbers, which can be achieved by a similar approach with a slight modification.
arrow_right_alt
Count subarrays with exactly k even numbers by transforming the problem to focus on even numbers instead of odd ones.
arrow_right_alt
Find the longest subarray with exactly k odd numbers by adjusting the approach to track the maximum length instead of counting subarrays.

help

常见问题

外企场景

继续练习

#1442 形成两个异或相等数组的三元组数目 #930 和相同的二元子数组 #1658 将 x 减到 0 的最小操作数