LeetCode 2488. 统计中位数为 K 的子数组 C#
原题链接
困难
作者:
hpstory
,
2022-11-29 10:51:27
,
所有人可见
,
阅读 166
C# 代码
public class Solution {
public int CountSubarrays(int[] nums, int k) {
int n = nums.Length;
int[] s = new int[n];
int t = 0;
for (int i = 0; i < n; i++){
if (nums[i] == k){
s[i] = 0;
t = i;
}
else if (nums[i] < k){
s[i] = -1;
}
else {
s[i] = 1;
}
}
Dictionary<int, int> dict = new Dictionary<int, int>();
// left, right模拟前后缀和数组
// k自己也算一个结果,result初始化为1
// k作为中位数时, 子数组在s中的和为0或者1
int left = 0, right = 0;
int result = 1;
for (int i = t - 1; i >= 0; i--){
left = s[i] + left;
if (left == 0 || left == 1) result++;
if (!dict.ContainsKey(left)) dict.Add(left, 0);
dict[left]++;
}
for (int i = t + 1; i < n; i++){
right = s[i] + right;
if (right == 0 || right == 1) result++;
if (dict.ContainsKey(-right)) result += dict[-right];
if (dict.ContainsKey(1 - right)) result += dict[1 - right];
}
return result;
}
}