LeetCode_前缀和_哈希表_困难_2488.统计中位数为 K 的子数组

￡神魔★判官ぃ 2023-10-08 20:24 37阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个长度为 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 中的整数互不相同

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/count-subarrays-with-median-k

## 2.思路 ##

（1）前缀和 & 哈希表  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————前缀和 & 哈希表
    class Solution {
        
        public int countSubarrays(int[] nums, int k) {
        
            int length = nums.length;
            //kIndex 表示正整数 k 在数组 nums 中的下标
            int kIndex = -1;
            for (int i = 0; i < length; i++) {
        
                if (nums[i] == k) {
        
                    kIndex = i;
                    break;
                }
            }
            int res = 0;
            //记录转换后的数组的每个前缀和以及对应出现的次数
            Map<Integer, Integer> counts = new HashMap<>();
            counts.put(0, 1);
            int sum = 0;
            for (int i = 0; i < length; i++) {
        
                // sum 表示转换后的数组 nums[0...i] 之和
                sum += Integer.compare(nums[i], k);
                if (i < kIndex) {
        
                    //下标 i + 1 可以作为中位数等于 k 的非空子数组的开始下标，将 sum 在哈希表中的出现次数加 1
                    counts.put(sum, counts.getOrDefault(sum, 0) + 1);
                } else {
        
                    /*
                        下标 i 可以作为中位数等于 k 的非空子数组的结束下标，从哈希表中获得前缀和 sum 的出现
                        次数 prev0 与前缀和 sum − 1 的出现次数 prev1，则以下标 i 作为结束下标且中位数等于 
                        k 的非空子数组的数目是 prev0 + prev1，将答案增加 prev0 + prev1
                    */
                    int prev0 = counts.getOrDefault(sum, 0);
                    int prev1 = counts.getOrDefault(sum - 1, 0);
                    res += prev0 + prev1;
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/count-subarrays-with-median-k/solution/tong-ji-zhong-wei-shu-wei-k-de-zi-shu-zu-ryix/