C++前缀和算法的应用：统计中位数为 K 的子数组

class Solution {
public:
int countSubarrays(vector& nums, const int k) {
m_c = nums.size();
vector vSum = { 0 };//Vsum[i]记录nums[0,i)中小于k的数量
for (const auto& n : nums)
{
vSum.emplace_back(vSum.back() + (n < k));
}
unordered_map<int, int> mLeftEven, mLeftOdd;
int left = 0;
for (; left < m_c; left++)
{
auto& m = (left & 1) ? mLeftOdd : mLeftEven;
m[left - 2 * vSum[left]]++;
if (k == nums[left])
{
break;
}
}
int iRet = 0;
for (int r = left; r < m_c; r++)
{
const int tmp = r - 2 * vSum[r + 1];
auto& mLenOdd = (r & 1) ? mLeftOdd : mLeftEven;
auto& mLenEven = (r & 1) ? mLeftEven : mLeftOdd;
iRet += mLenOdd[tmp] + mLenEven[tmp - 1];
std::cout << “r:” << r << " 奇数：" << mLenOdd.count(tmp) << " 偶数：" << mLenEven.count(tmp - 1) << std::endl;
}
return iRet;
}
int m_c;
};

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
Solution slu;
vector nums;
int res;
nums = { 5,11,4,6,2,7,10,8,1,3,9,12 };
res = slu.countSubarrays(nums, 6);
Assert(22, res);
nums = { 2,3,1 };
res = slu.countSubarrays(nums, 3);
Assert(1, res);
nums = { 3,2,1,4,5 };
res = slu.countSubarrays(nums, 4);
Assert(3, res);

class Solution {
public:
int countSubarrays(vector& nums, int k) {
m_c = nums.size();
//大于K的数减小于K
std::unordered_map<int, int> mSubNum;
mSubNum[0] = 1;
int i = 0;
int iGreate = 0, iLess = 0;
for (; (i < m_c)&&( nums[i] != k ) ; i++)
{
iGreate += nums[i] > k;
iLess += nums[i] < k;
mSubNum[iGreate - iLess]++;
}
int iRet = 0;
for (; i < m_c; i++)
{
iGreate += nums[i] > k;
iLess += nums[i] < k;
iRet += mSubNum[iGreate - iLess];
iRet += mSubNum[iGreate - iLess-1];
}
return iRet;
}
int m_c;
};