题目描述：
给出一个长度为 $ n $ 的数组nums，该数组由 $ 1,\cdots,n $ 的不同数字组成，是一个排列。给出正整数 $ k $ ，统计数组中中位数等于 $ k $ 的非空子数组的数目。（偶数长度时，中位数指中间靠左的元素）。
数据范围：
$ 1\le n \le 10^5 $
题解：
首先想到了使用经典前缀和加哈希统计子区间和的性质。为了使用和，需要将原数组进行处理，严格大于 $ k $ 的置为 $ 1 $ ，严格小于 $ k $ 的置为 $ -1 $ ，等于 $ k $ 的置为 $ 0 $ 。后续如果一个子区间的和等于 $ 0 $ 或 $ 1 $ 并且包含 $ k $ 就对答案加一。使用哈希表记录前缀和值出现的次数。
统计区间中 $ k $ 的个数，但是这样的话需要遍历哈希表中当前值的起始位置。
注意到 $ k $ 只存在一个，这样的话就可以将区间分为两部分 $ [0, k),[k, n) $ 。在前一部分区间只需要统计前缀和值出现的次数，后半部分则统计 $ sum,sum-1 $ 出现的次数，然后加到答案上面。
注意初始化mp[0] = 1，未曾遍历数组时就已经存在前缀和为 $ 0 $ 的值了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
unordered_map<int, int> mp;
int countSubarrays(vector<int> &nums, int k)
{
int index = 0;
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] > k)
nums[i] = 1;
else if (nums[i] == k)
nums[i] = 0, index = i;
else
nums[i] = -1;
}
int tmp = 0, ans = 0;
mp[0] = 1;
for (int i = 0; i < nums.size(); ++i)
{
tmp += nums[i];
if (i >= index)
{
if (mp.count(tmp))
{
ans += mp[tmp];
}
if (mp.count(tmp - 1))
{
ans += mp[tmp - 1];
}
}
else if (i < index)
mp[tmp]++;
}
return ans;
}
};
|