力扣2488.統(tǒng)計中位數(shù)為 K 的子數(shù)組

• 等價轉(zhuǎn)換

  • 子數(shù)組為奇數(shù) ： 左小 + 右小 = 左大 + 右大
    • 左小 – 左大 = 右大 – 右小
  • 子數(shù)組為偶數(shù) ： 左小 + 右小 = 左大 + 右大 – 1
    • 左小 – 左大 = 右大 – 右小 - 1
    • 提示中說明k為兩數(shù)中左邊那個
  • 先從k的下標(biāo)pos開始往左逆序求左權(quán)值
  • 再從pos開始往右正序求有權(quán)值
    • 求的過程中res加上以當(dāng)前i為右端點的奇偶兩種區(qū)間

•   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;}};