力扣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 左大为-1
              x += 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 右小为-1
              x += nums[i] > k ? 1 : -1;
              //一奇一偶
              res += cnt[x] + cnt[x - 1];
          }
          return res;
      }
  };