力扣2488.统计中位数为 K 的子数组

力扣2488.统计中位数为 K 的子数组

• 等价转换

  • 子数组为奇数 ： 左小 + 右小 = 左大 + 右大
    • 左小 – 左大 = 右大 – 右小
  • 子数组为偶数 ： 左小 + 右小 = 左大 + 右大 – 1
    • 左小 – 左大 = 右大 – 右小 - 1
    • 提示中说明k为两数中左边那个
  • 先从k的下标pos开始往左逆序求左权值
  • 再从pos开始往右正序求有权值
    • 求的过程中res加上以当前i为右端点的奇偶两种区间

•   class Solution {public:int countSubarrays(vector<int>& nums, int k) {int pos = find(nums.begin(),nums.end(),k) - nums.begin();  unordered_map<int,int> cnt{{0,1}};for(int i= pos - 1,x=0;i>=0;i--){//左小为1 左大为-1x += nums[i] < k ? 1 : -1;cnt[x] ++;}int res = cnt[0] + cnt[-1];for(int i=pos + 1,x=0;i<nums.size();i++){//右大为1 右小为-1x += nums[i] > k ? 1 : -1;//一奇一偶res += cnt[x] + cnt[x - 1];}return res;}};