前缀和 哈希表 思维
题目要求出 一段子数组排序后中位数为 k
的个数
因为题目不关心绝对大小,只关心相对大小。所以
nums[i] <= k nums[i] = -1
nums[i] > k nums[i] = 1
将问题转化为,求子数组全部和为0(偶数) 或者 -1(奇数)的个数
即 求 [l, r]
前缀和满足条件的个数, 0 <= l <= k <= r
易得 S = sr - s(l - 1), -1 <= l - 1 < k
, 则求S = 0 | -1
的个数,等价于求s(l-1) == sr | sr + 1
的个数
从左到右开始计算前缀和,并通过哈希表记录个数,直到 nums[i] == k
,停止记录。
初始化:h[0] = 1
简易的前缀和示例
s s-1 s s+1 s s-1 s-2 s-1 s s+1 s(k) s+1...s+1(sr)...
, l - 1 < k,即当区间右端点确定,求s(l-1) == sr | sr + 1
的个数 ,示例,示例答案为2
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> h;
h[0] = 1;
bool f = false;
int s = 0, ans = 0;
for (int i = 0; i < n; i ++) {
s += nums[i] > k ? 1 : -1;
if (nums[i] == k) f = true;
if (f) ans += h[s] + h[s + 1];
else ++ h[s];
}
return ans;
}
};