题目
给你一个长度为 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
中的整数互不相同
分割线-下方题解可以自己思考思考再看答案
分割线尾部-下方题解
方法一:前缀和
由于数组 nums 的长度是 n ,数组由从 1 到 n 的不同整数组成,因此数组中的元素各不相同,满足 1 小于等于 K 小于等于 n 的正整数 K 的数组中恰好出现一次。
用 kIndex 表示正整数 K 在数组 nums 中下标。根据中位数的定义,中位数等于 K 的非空子数组应满足以下条件:
- 子数组的开始下标小于等于 kIndex 且结束下标大于等于 kIndex ;
- 子数组中的大于 K 的元素个数与小于 K 的元素个数之差为 0 或 1.
为了计算每个子数组中的大于 K 的元素个数与小于 K 的元素个数之差,需要将原始数组做转换,将大于 K 的元素转换成 1 ,小于 K 的元素转换成 -1 ,等于 K 的元素转换成 0 ,转换后的数组中,每个子数组的元素和为对应的原始子数组中的大于 K 的元素个数与小于 K 的元素个数之差。
为了在转换后的数组中寻找符号要求的子数组,可以计算转换后的数组的前缀和。感觉前缀和寻找符号要求的子数组。规定空前缀的前缀和是 0 且对应下标 -1 。
如果存在下标 left 和 right 满足 -1 小于等于 left 小于等于 kIndex 小于等于 right 小于等于 n 且下标 right 处的前缀和与下标 left 处的前缀和之差为 0 或 1,则等价与下标范围 [left + 1,right] 包含下标 kIndex 且该下标范围的转换后的子数组的元素和为 0 或 1,对应该下标范围的原始子数组的中位数等于 K。
根据上述分析,可以从左到右遍历数组 nums , 遍历过程中计算转换后的数组的前缀和,并计算中位数等于 K 的非空子数组的数目。
使用哈希表记录转换后的数组的每个前缀和的出现次数。由于空前缀的前缀和是 0 ,因此首先将前缀和 0 与次数 1 存入哈希表。
用 sum 表示转换后的数组的前缀和,遍历过程中维护 sum 的值。对于 0 小于等于 i 小于等于 n ,当遍历到下标 i 时,更新 sum 的值,然后执行如下操作:
- 如果 i < kIndex ,则下标 i + 1 可以作为中位数等于 K 的非空子数组的开始下标,将 sum 在哈希表中的出现次数加 1 ;
- 如果 i 大于等于 kIndex ,则下标 i 可以作为中位数等于 K 的非空子数组的结束下标,从哈希表中获得前缀和 sum 的出现次数 prev0 与前缀和sum - 1 的出现次数 prev1 ,则以下标 i 作为结束下标且中位数等于 K 的非空子数组的数目是 prev0 + prev1 ,将答案增加 prev0 + prev1 。
遍历结束之后,即可得到中位数等于 K 的非空子数组的数目。
答案:
Python↓
class Solution:def sign(self, num: int) -> int:return (num > 0) - (num < 0)def countSubarrays(self, nums: List[int], k: int) -> int:kIndex = nums.index(k)ans = 0counts = Counter()counts[0] = 1sum = 0for i, num in enumerate(nums):sum += self.sign(num - k)if i < kIndex:counts[sum] += 1else:prev0 = counts[sum]prev1 = counts[sum - 1]ans += prev0 + prev1return ansclass Solution: def sign(self, num: int) -> int: return (num > 0) - (num < 0) def countSubarrays(self, nums: List[int], k: int) -> int: kIndex = nums.index(k) ans = 0 counts = Counter() counts[0] = 1 sum = 0 for i, num in enumerate(nums): sum += self.sign(num - k) if i < kIndex: counts[sum] += 1 else: prev0 = counts[sum] prev1 = counts[sum - 1] ans += prev0 + prev1 return ansclass Solution: def sign(self, num: int) -> int: return (num > 0) - (num < 0) def countSubarrays(self, nums: List[int], k: int) -> int: kIndex = nums.index(k) ans = 0 counts = Counter() counts[0] = 1 sum = 0 for i, num in enumerate(nums): sum += self.sign(num - k) if i < kIndex: counts[sum] += 1 else: prev0 = counts[sum] prev1 = counts[sum - 1] ans += prev0 + prev1 return ans
JAVA↓
class Solution {public int countSubarrays(int[] nums, int k) {int n = nums.length;int kIndex = -1;for (int i = 0; i < n; i++) {if (nums[i] == k) {kIndex = i;break;}}int ans = 0;Map<Integer, Integer> counts = new HashMap<Integer, Integer>();counts.put(0, 1);int sum = 0;for (int i = 0; i < n; i++) {sum += sign(nums[i] - k);if (i < kIndex) {counts.put(sum, counts.getOrDefault(sum, 0) + 1);} else {int prev0 = counts.getOrDefault(sum, 0);int prev1 = counts.getOrDefault(sum - 1, 0);ans += prev0 + prev1;}}return ans;}public int sign(int num) {if (num == 0) {return 0;}return num > 0 ? 1 : -1;}}class Solution { public int countSubarrays(int[] nums, int k) { int n = nums.length; int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); counts.put(0, 1); int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts.put(sum, counts.getOrDefault(sum, 0) + 1); } else { int prev0 = counts.getOrDefault(sum, 0); int prev1 = counts.getOrDefault(sum - 1, 0); ans += prev0 + prev1; } } return ans; } public int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } }class Solution { public int countSubarrays(int[] nums, int k) { int n = nums.length; int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); counts.put(0, 1); int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts.put(sum, counts.getOrDefault(sum, 0) + 1); } else { int prev0 = counts.getOrDefault(sum, 0); int prev1 = counts.getOrDefault(sum - 1, 0); ans += prev0 + prev1; } } return ans; } public int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } }
C#↓
public class Solution {public int CountSubarrays(int[] nums, int k) {int n = nums.Length;int kIndex = -1;for (int i = 0; i < n; i++) {if (nums[i] == k) {kIndex = i;break;}}int ans = 0;IDictionary<int, int> counts = new Dictionary<int, int>();counts.Add(0, 1);int sum = 0;for (int i = 0; i < n; i++) {sum += sign(nums[i] - k);if (i < kIndex) {if (!counts.ContainsKey(sum)) {counts.Add(sum, 1);} else {counts[sum]++;}} else {int prev0 = counts.ContainsKey(sum) ? counts[sum] : 0;int prev1 = counts.ContainsKey(sum - 1) ? counts[sum - 1] : 0;ans += prev0 + prev1;}}return ans;}public int sign(int num) {if (num == 0) {return 0;}return num > 0 ? 1 : -1;}}public class Solution { public int CountSubarrays(int[] nums, int k) { int n = nums.Length; int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; IDictionary<int, int> counts = new Dictionary<int, int>(); counts.Add(0, 1); int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { if (!counts.ContainsKey(sum)) { counts.Add(sum, 1); } else { counts[sum]++; } } else { int prev0 = counts.ContainsKey(sum) ? counts[sum] : 0; int prev1 = counts.ContainsKey(sum - 1) ? counts[sum - 1] : 0; ans += prev0 + prev1; } } return ans; } public int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } }public class Solution { public int CountSubarrays(int[] nums, int k) { int n = nums.Length; int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; IDictionary<int, int> counts = new Dictionary<int, int>(); counts.Add(0, 1); int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { if (!counts.ContainsKey(sum)) { counts.Add(sum, 1); } else { counts[sum]++; } } else { int prev0 = counts.ContainsKey(sum) ? counts[sum] : 0; int prev1 = counts.ContainsKey(sum - 1) ? counts[sum - 1] : 0; ans += prev0 + prev1; } } return ans; } public int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } }
C++↓
class Solution {public:inline int sign(int num) {if (num == 0) {return 0;}return num > 0 ? 1 : -1;}int countSubarrays(vector<int>& nums, int k) {int n = nums.size();int kIndex = -1;for (int i = 0; i < n; i++) {if (nums[i] == k) {kIndex = i;break;}}int ans = 0;unordered_map<int, int> counts;counts[0] = 1;int sum = 0;for (int i = 0; i < n; i++) {sum += sign(nums[i] - k);if (i < kIndex) {counts[sum]++;} else {int prev0 = counts[sum];int prev1 = counts[sum - 1];ans += prev0 + prev1;}}return ans;}};class Solution { public: inline int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } int countSubarrays(vector<int>& nums, int k) { int n = nums.size(); int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; unordered_map<int, int> counts; counts[0] = 1; int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts[sum]++; } else { int prev0 = counts[sum]; int prev1 = counts[sum - 1]; ans += prev0 + prev1; } } return ans; } };class Solution { public: inline int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } int countSubarrays(vector<int>& nums, int k) { int n = nums.size(); int kIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; unordered_map<int, int> counts; counts[0] = 1; int sum = 0; for (int i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts[sum]++; } else { int prev0 = counts[sum]; int prev1 = counts[sum - 1]; ans += prev0 + prev1; } } return ans; } };
C语言↓
typedef struct {int key;int val;UT_hash_handle hh;} HashItem;HashItem *hashFindItem(HashItem **obj, int key) {HashItem *pEntry = NULL;HASH_FIND_INT(*obj, &key, pEntry);return pEntry;}bool hashAddItem(HashItem **obj, int key, int val) {if (hashFindItem(obj, key)) {return false;}HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));pEntry->key = key;pEntry->val = val;HASH_ADD_INT(*obj, key, pEntry);return true;}bool hashSetItem(HashItem **obj, int key, int val) {HashItem *pEntry = hashFindItem(obj, key);if (!pEntry) {hashAddItem(obj, key, val);} else {pEntry->val = val;}return true;}int hashGetItem(HashItem **obj, int key, int defaultVal) {HashItem *pEntry = hashFindItem(obj, key);if (!pEntry) {return defaultVal;}return pEntry->val;}void hashFree(HashItem **obj) {HashItem *curr = NULL, *tmp = NULL;HASH_ITER(hh, *obj, curr, tmp) {HASH_DEL(*obj, curr);free(curr);}}static inline int sign(int num) {if (num == 0) {return 0;}return num > 0 ? 1 : -1;}int countSubarrays(int* nums, int numsSize, int k) {int kIndex = -1;for (int i = 0; i < numsSize; i++) {if (nums[i] == k) {kIndex = i;break;}}int ans = 0;HashItem *counts = NULL;hashAddItem(&counts, 0, 1);int sum = 0;for (int i = 0; i < numsSize; i++) {sum += sign(nums[i] - k);if (i < kIndex) {hashSetItem(&counts, sum, hashGetItem(&counts, sum, 0) + 1);} else {int prev0 = hashGetItem(&counts, sum, 0);int prev1 = hashGetItem(&counts, sum - 1, 0);ans += prev0 + prev1;}}hashFree(&counts);return ans;}typedef struct { int key; int val; UT_hash_handle hh; } HashItem; HashItem *hashFindItem(HashItem **obj, int key) { HashItem *pEntry = NULL; HASH_FIND_INT(*obj, &key, pEntry); return pEntry; } bool hashAddItem(HashItem **obj, int key, int val) { if (hashFindItem(obj, key)) { return false; } HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem)); pEntry->key = key; pEntry->val = val; HASH_ADD_INT(*obj, key, pEntry); return true; } bool hashSetItem(HashItem **obj, int key, int val) { HashItem *pEntry = hashFindItem(obj, key); if (!pEntry) { hashAddItem(obj, key, val); } else { pEntry->val = val; } return true; } int hashGetItem(HashItem **obj, int key, int defaultVal) { HashItem *pEntry = hashFindItem(obj, key); if (!pEntry) { return defaultVal; } return pEntry->val; } void hashFree(HashItem **obj) { HashItem *curr = NULL, *tmp = NULL; HASH_ITER(hh, *obj, curr, tmp) { HASH_DEL(*obj, curr); free(curr); } } static inline int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } int countSubarrays(int* nums, int numsSize, int k) { int kIndex = -1; for (int i = 0; i < numsSize; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; HashItem *counts = NULL; hashAddItem(&counts, 0, 1); int sum = 0; for (int i = 0; i < numsSize; i++) { sum += sign(nums[i] - k); if (i < kIndex) { hashSetItem(&counts, sum, hashGetItem(&counts, sum, 0) + 1); } else { int prev0 = hashGetItem(&counts, sum, 0); int prev1 = hashGetItem(&counts, sum - 1, 0); ans += prev0 + prev1; } } hashFree(&counts); return ans; }typedef struct { int key; int val; UT_hash_handle hh; } HashItem; HashItem *hashFindItem(HashItem **obj, int key) { HashItem *pEntry = NULL; HASH_FIND_INT(*obj, &key, pEntry); return pEntry; } bool hashAddItem(HashItem **obj, int key, int val) { if (hashFindItem(obj, key)) { return false; } HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem)); pEntry->key = key; pEntry->val = val; HASH_ADD_INT(*obj, key, pEntry); return true; } bool hashSetItem(HashItem **obj, int key, int val) { HashItem *pEntry = hashFindItem(obj, key); if (!pEntry) { hashAddItem(obj, key, val); } else { pEntry->val = val; } return true; } int hashGetItem(HashItem **obj, int key, int defaultVal) { HashItem *pEntry = hashFindItem(obj, key); if (!pEntry) { return defaultVal; } return pEntry->val; } void hashFree(HashItem **obj) { HashItem *curr = NULL, *tmp = NULL; HASH_ITER(hh, *obj, curr, tmp) { HASH_DEL(*obj, curr); free(curr); } } static inline int sign(int num) { if (num == 0) { return 0; } return num > 0 ? 1 : -1; } int countSubarrays(int* nums, int numsSize, int k) { int kIndex = -1; for (int i = 0; i < numsSize; i++) { if (nums[i] == k) { kIndex = i; break; } } int ans = 0; HashItem *counts = NULL; hashAddItem(&counts, 0, 1); int sum = 0; for (int i = 0; i < numsSize; i++) { sum += sign(nums[i] - k); if (i < kIndex) { hashSetItem(&counts, sum, hashGetItem(&counts, sum, 0) + 1); } else { int prev0 = hashGetItem(&counts, sum, 0); int prev1 = hashGetItem(&counts, sum - 1, 0); ans += prev0 + prev1; } } hashFree(&counts); return ans; }
JavaScript↓
var countSubarrays = function(nums, k) {const n = nums.length;let kIndex = -1;for (let i = 0; i < n; i++) {if (nums[i] === k) {kIndex = i;break;}}let ans = 0;const counts = new Map();counts.set(0, 1);let sum = 0;for (let i = 0; i < n; i++) {sum += sign(nums[i] - k);if (i < kIndex) {counts.set(sum, (counts.get(sum) || 0) + 1);} else {const prev0 = (counts.get(sum) || 0);const prev1 = (counts.get(sum - 1) || 0);ans += prev0 + prev1;}}return ans;}const sign = (num) => {if (num === 0) {return 0;}return num > 0 ? 1 : -1;};var countSubarrays = function(nums, k) { const n = nums.length; let kIndex = -1; for (let i = 0; i < n; i++) { if (nums[i] === k) { kIndex = i; break; } } let ans = 0; const counts = new Map(); counts.set(0, 1); let sum = 0; for (let i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts.set(sum, (counts.get(sum) || 0) + 1); } else { const prev0 = (counts.get(sum) || 0); const prev1 = (counts.get(sum - 1) || 0); ans += prev0 + prev1; } } return ans; } const sign = (num) => { if (num === 0) { return 0; } return num > 0 ? 1 : -1; };var countSubarrays = function(nums, k) { const n = nums.length; let kIndex = -1; for (let i = 0; i < n; i++) { if (nums[i] === k) { kIndex = i; break; } } let ans = 0; const counts = new Map(); counts.set(0, 1); let sum = 0; for (let i = 0; i < n; i++) { sum += sign(nums[i] - k); if (i < kIndex) { counts.set(sum, (counts.get(sum) || 0) + 1); } else { const prev0 = (counts.get(sum) || 0); const prev1 = (counts.get(sum - 1) || 0); ans += prev0 + prev1; } } return ans; } const sign = (num) => { if (num === 0) { return 0; } return num > 0 ? 1 : -1; };
Go语言↓
func countSubarrays(nums []int, k int) int {kIndex := -1for i, num := range nums {if num == k {kIndex = ibreak}}ans := 0counts := map[int]int{}counts[0] = 1sum := 0for i, num := range nums {sum += sign(num - k)if i < kIndex {counts[sum]++} else {prev0 := counts[sum]prev1 := counts[sum-1]ans += prev0 + prev1}}return ans}func sign(num int) int {if num == 0 {return 0}if num > 0 {return 1}return -1}func countSubarrays(nums []int, k int) int { kIndex := -1 for i, num := range nums { if num == k { kIndex = i break } } ans := 0 counts := map[int]int{} counts[0] = 1 sum := 0 for i, num := range nums { sum += sign(num - k) if i < kIndex { counts[sum]++ } else { prev0 := counts[sum] prev1 := counts[sum-1] ans += prev0 + prev1 } } return ans } func sign(num int) int { if num == 0 { return 0 } if num > 0 { return 1 } return -1 }func countSubarrays(nums []int, k int) int { kIndex := -1 for i, num := range nums { if num == k { kIndex = i break } } ans := 0 counts := map[int]int{} counts[0] = 1 sum := 0 for i, num := range nums { sum += sign(num - k) if i < kIndex { counts[sum]++ } else { prev0 := counts[sum] prev1 := counts[sum-1] ans += prev0 + prev1 } } return ans } func sign(num int) int { if num == 0 { return 0 } if num > 0 { return 1 } return -1 }
不要问为什么只有这几种答案,问就是作者目前只掌握这几个哦~ (嘻~
哈希表不懂的小伙伴可以去网上搜搜了解一下,或者下方评论一下我再出一个帖子发哈希表的- ̗̀(๑ᵔ⌔ᵔ๑)( •͈ᴗ⁃͈)ᓂ- - -♡