本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。
注意：
数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
示例 2：
输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。
参数范围：
n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
nums 中的整数互不相同
分析
变量解释
| vSum[i] | 记录nums[0,i)中小于k的数量 |
| mLeftOdd | left为奇数的：l - 2*vSum[l] |
| mLeftEven | left为偶数的：l - 2*vSum[l] |
| mLenOdd | 长度为奇数的：l - 2*vSum[l] |
| mLenEven | 长度为偶数的：l - 2*vSum[l] |
奇偶性
| left为奇数 | r为奇数 | 长度为奇数 |
| left为奇数 | r为偶数 | 长度为偶数 |
| left为偶数 | r为奇数 | 长度为偶数 |
| left为偶数 | r为偶数 | 长度为奇数 |
原理
假定nums[kIndex]等于k，则包括k的子数组可以表示为：nums[left,right]，left的取值范围为(-1,kIndex]，right的取值范围为[kIndex,m_c)。
| nums[l,r]的长度： r-l+1。 |
| nums[l,r]中小于k的数量: vSum[r+1]-vSum[l]。 |
| 如果长度是奇数：（长度-1）/2== k的数量 则符合要求 => r-l = 2*(vSum[r+1]-vSum[l]) |
| 如果长度是偶数：（长度-2）/2 == k的数量 则符合要求 => r-l-1 = 2*(vSum[r+1]-vSum[l]) |
| 将l相关移到右边：r - 2vSum[r+1] = l - 2vSum[l]; r - 2vSum[r+1]-1 = l - 2vSum[l] |
代码
核心代码
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);
//CConsole::Out(res);
}
2023年4月版
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; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 充满正能量得对大家说
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
