DeepSeek LeetCode 2488. 统计中位数为 K 的子数组 public int countSubarrays(int[] nums, int k)

这道题要求统计所有子数组中中位数等于 k 的子数组个数。核心思路先找到 k 在数组中的位置pos中位数定义对于奇数长度排序后中间的数 k等价转换对于子数组比 k 小的数个数 比 k 大的数个数奇数长度或差为1偶数长度但题目默认奇数长度需确认实际上 LeetCode 2488 的定义子数组长度为奇数时中位数是中间元素长度偶数时中位数定义为中间靠左那个。但要注意题目统计的是中位数为 k的子数组所以 k 必须出现在子数组中并且整个子数组中小于 k 的数字个数 大于 k 的数字个数当子数组长度为奇数小于 k 的数字个数 大于 k 的数字个数 - 1当子数组长度为偶数时k 在左中位但更简单的统一方法是将比 k 大的数记为 1比 k 小的数记为 -1等于 k 的记为 0。那么对于包含 k 的子数组左部分和 右部分和 0奇数长度或 1偶数长度k 在左中位。实际上题解标准做法是算法找到 k 的位置 idx从 idx 向左扫描维护「大于 k 的数量 - 小于 k 的数量」的差值存入哈希表从 idx 向右扫描用同样的方式计算并与左边组合代码实现publicintcountSubarrays(int[]nums,intk){intnnums.length;intpos-1;// 找到 k 的位置for(inti0;in;i){if(nums[i]k){posi;break;}}// map 存储左边出现的平衡值及次数MapInteger,IntegerleftMapnewHashMap();leftMap.put(0,1);// 空子数组只包含 k 自身intbalance0;// 向左遍历for(intipos-1;i0;i--){if(nums[i]k){balance;}elseif(nums[i]k){balance--;}leftMap.put(balance,leftMap.getOrDefault(balance,0)1);}intresult0;balance0;// 向右遍历并统计for(intipos;in;i){if(ipos){// 避免重复处理 pos 位置if(nums[i]k){balance;}elseif(nums[i]k){balance--;}}// 需要左边 balance -balance奇数长度// 或者 balance 1 - balance偶数长度k 在左边resultleftMap.getOrDefault(-balance,0);resultleftMap.getOrDefault(1-balance,0);}returnresult;}解释balance表示当前区间内「大于 k 的数个数 - 小于 k 的数个数」当子数组长度为奇数平衡应为 0即leftBalance rightBalance 0当子数组长度为偶数k 在左中位应满足leftBalance rightBalance 1leftMap存储从 k 往左的每种平衡值的出现次数包括空区间向右扩展时对每个右边界找左边界使得上面两式成立时间复杂度O(n)空间复杂度O(n)示例nums [3,2,1,4,5], k 4pos 3向左平衡值变化-1, -2, -1得到 leftMap: {0:1, -1:2, -2:1}向右遍历i3, balance0: 需要 left 0 和 1得 101i4, balance1: 需要 left -1 和 0得 213总数4