LeetCode 2488. 【妙】统计中位数为 K 的子数组
原题链接
困难
作者:
α_29
,
2023-03-16 17:20:54
,
所有人可见
,
阅读 127
class Solution {
public:
//k值右侧【大于k的个数】-【小于k的个数】== 0/1时,ans++;同理,左侧。
int countSubarrays(vector<int>& nums, int k) {
int i = find(nums.begin(),nums.end(),k) - nums.begin();
//x表示【大于k的个数】-【小于k的个数】范围是[-n,n]
int n = nums.size(), ans = 1, x = 0;
//2n+1个数组,将[-n,n]改为[0,2n]
int cnt[n<<1|1];//cnt[x]表示【大于k的个数】-【小于k的个数】= x 的数组数量
memset(cnt,0,sizeof cnt);
//k的右侧
for(int j = i + 1; j < n; j ++){
x += nums[j] > k ? 1 : -1;
if(!x || x == 1) ans++;
cnt[x + n] ++;
}
//k的左侧 和 左右两侧
x = 0;
for(int j = i - 1; j >= 0 ;j--){
x += nums[j] > k ? 1 : -1;
if(!x || x == 1) ans ++;
/*
注意:题目中不仅只 分别 对i左右两侧的子数组,还要对i左右两侧 同时 组成数组的情况
所以如果此时的x对应的-x和-x+1已经在cnt中(在对k右侧的出来的-x和-x+1,即x-x=0,x-x+1=1),
则x和-x、-x+1的组合也是符合要求的
*/
ans += cnt[-x+n] + cnt[-x+1+n];//左右合璧的情况
}
return ans;
}
};