第328场周赛2537. 统计好子数组的数目
阿里云国际版折扣https://www.yundadi.com |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
原题链接统计好子数组的数目
给你一个整数数组 nums 和一个整数 k 请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] 那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
示例 1
输入nums = [1,1,1,1,1], k = 10
输出1
解释唯一的好子数组是这个数组本身。
示例 2
输入nums = [3,1,4,3,2,2,4], k = 2
输出4
解释总共有 4 个不同的好子数组
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。
提示
-
1 <= nums.length <= 10^5
-
1 <= nums[i], k <= 10^9
思路
1.下标[left,right]区间内如果满足条件了那么总长度n-right个都满足条件
2.此时left++以新的起点试图重新判断是否满足条件 再重复步骤1.
public static long countGood(int[] nums, int k) {
long ans=0;
int l=0,r=0,len=nums.length;
HashMap<Integer,Integer> map=new HashMap<>();
int has=0;
while (l<=r&&l<len){
while (has<k&&r<len){
has+=map.getOrDefault(nums[r],0);
map.put(nums[r],map.getOrDefault(nums[r],0)+1);
r++;
}
if (has>=k){
ans+=len-r+1;
}
int sub=nums[l];
map.put(sub,map.get(sub)-1);
has-=map.get(sub);
l++;
}
return ans;
}