力扣算法题第2461题:
长度为K子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列
思路(java)(滑动窗口):
先创建一个哈希表，用来保存每个值出现的次数，然后for循环，定义left来记录长度为K的子数组的最小下标值(刚开始会小于0)，循环到left>=0之后，进行滑动窗口，先判断哈希表的长度是否等于K，如果不等于就说明有重复数字，跳过这一条循环，如果哈希表的长度等于K，先取之前的值和现在的值的最大值，再对最左边的元素进行离开窗口操作，即若哈希表的值为1，去除这个键，否则让其值减一.
力扣参考答案:
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
long ans = 0;
long s = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 1. 进入窗口
s += nums[i];
cnt.merge(nums[i], 1, Integer::sum); // cnt[nums[i]]++
int left = i - k + 1;
if (left < 0) { // 窗口大小不足 k
continue;
}
// 2. 更新答案
if (cnt.size() == k) {
ans = Math.max(ans, s);
}
// 3. 离开窗口
int out = nums[left];
s -= out;
int c = cnt.get(out);
if (c > 1) {
cnt.put(out, c - 1);
} else {
cnt.remove(out);
}
}
return ans;
}
}
链接：https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/solutions/1951940/hua-dong-chuang-kou-by-endlesscheng-m0gm/