What is the optimal approach for solving 'Count Subarrays With Median K'?

The optimal approach is to transform the array using values 1, -1, and 0, then use a prefix sum and hash map to count subarrays with a sum of zero.

How do you handle large arrays in this problem?

For large arrays, the use of cumulative sum and hash maps ensures an O(n) time complexity, making the solution efficient even for the maximum input size.

What is the time complexity of the 'Count Subarrays With Median K' solution?

The time complexity is O(n) because the algorithm processes each element once and uses efficient hash map lookups for counting subarrays.

What are the key challenges in the 'Count Subarrays With Median K' problem?

The main challenge lies in transforming the array efficiently and using the right data structures, like hash maps, to track prefix sums and count valid subarrays.

How does the prefix sum technique work for this problem?

Prefix sum helps track the cumulative sum of transformed values. When a prefix sum repeats, it indicates the presence of a subarray with a zero sum, which corresponds to a valid subarray with median k.

#2488

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计中位数为 K 的子数组

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。统计并返回 nums 中的中位数等于 k 的非空子数组的数目。注意：数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素…

数组哈希表前缀和

题目描述

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。
- 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。

示例 1：

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

提示：

n == nums.length
1 <= n <= 10⁵
1 <= nums[i], k <= n
nums 中的整数互不相同

lightbulb

解题思路

方法一：遍历 + 计数

我们先找到中位数 $k$ 在数组中的位置 $i$ ，然后从 $i$ 开始向两边遍历，统计中位数为 $k$ 的子数组的数目。

定义一个答案变量 $ans$ ，表示中位数为 $k$ 的子数组的数目。初始时 $ans = 1$ ，表示当前有一个长度为 $1$ 的子数组，其中位数为 $k$ 。另外，定义一个计数器 $cnt$ ，用于统计当前遍历过的数组中，「比 $k$ 大的元素的个数」与「比 $k$ 小的元素的个数」的差值的个数。

接下来，从 $i + 1$ 开始向右遍历，我们维护一个变量 $x$ ，表示当前右侧子数组中「比 $k$ 大的元素的个数」与「比 $k$ 小的元素的个数」的差值。如果 $x \in [0, 1]$ ，则当前右侧子数组的中位数为 $k$ ，答案变量 $ans$ 自增 $1$ 。然后，我们将 $x$ 的值加入计数器 $cnt$ 中。

同理，从 $i - 1$ 开始向左遍历，同样维护一个变量 $x$ ，表示当前左侧子数组中「比 $k$ 大的元素的个数」与「比 $k$ 小的元素的个数」的差值。如果 $x \in [0, 1]$ ，则当前左侧子数组的中位数为 $k$ ，答案变量 $ans$ 自增 $1$ 。如果 $-x$ 或 $-x + 1$ 也在计数器中，说明当前存在跨越 $i$ 左右两侧的子数组，其中位数为 $k$ ，答案变量 $ans$ 增加计数器中对应的值，即 $ans += cnt[-x] + cnt[-x + 1]$ 。

最后，返回答案变量 $ans$ 即可。

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

在编码上，我们可以直接开一个长度为 $2 \times n + 1$ 的数组，用于统计当前数组中，比 $k$ 大的元素的个数与比 $k$ 小的元素的个数的差值，每一次我们将差值加上 $n$ ，即可将差值的范围从 $[-n, n]$ 转换为 $[0, 2n]$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        i = nums.index(k)
        cnt = Counter()
        ans = 1
        x = 0
        for v in nums[i + 1 :]:
            x += 1 if v > k else -1
            ans += 0 <= x <= 1
            cnt[x] += 1
        x = 0
        for j in range(i - 1, -1, -1):
            x += 1 if nums[j] > k else -1
            ans += 0 <= x <= 1
            ans += cnt[-x] + cnt[-x + 1]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate effectively leverages the array transformation to simplify the median problem.
question_mark
The candidate is comfortable using hash maps to track prefix sums and identify subarrays.
question_mark
The candidate is able to explain the trade-off between brute force methods and the efficient use of prefix sums and hash lookups.

warning

常见陷阱

外企场景

error
Not recognizing that the problem can be reduced to finding subarrays with a sum of zero.
error
Misunderstanding the transformation of the array into 1, -1, and 0 values.
error
Failing to efficiently count subarrays with hash maps, leading to time complexity issues.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider adding duplicate values in the array and adjusting the approach accordingly.
arrow_right_alt
Explore the possibility of applying the solution to non-distinct integer arrays.
arrow_right_alt
Modify the problem to allow for non-zero medians in subarrays, which could require different transformation or counting logic.

help

常见问题

外企场景

继续练习

#2588 统计美丽子数组数目 #2615 等值距离和 #2251 花期内花的数目