Day7--滑动窗口与双指针--1695. 删除子数组的最大得分，2958. 最多 K 个重复元素的最长子数组，2024. 考试的最大困扰度
Day7–滑动窗口与双指针–1695. 删除子数组的最大得分，2958. 最多 K 个重复元素的最长子数组，2024. 考试的最大困扰度
今天要训练的题目类型是：【不定长滑动窗口】，题单来自@灵艾山茶府。
滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。
不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。
今天的题目类型是：求最长子数组。
1695. 删除子数组的最大得分
思路【我】：
- 题意：就是求最大子数组和，数组里面不能有相同的元素
- 不定长滑动窗口三步曲：入–出–更新
class Solution {public int maximumUniqueSubarray(int[] nums) {// 题意：就是求最大子数组和，数组里面不能有相同的元素int n = nums.length;int sum = 0;int maxSum = 0;int left = 0;// 利用map<元素，出现次数>记录窗口内元素的出现次数Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {// 1，入sum += nums[i];map.merge(nums[i], 1, Integer::sum);// 2，出while (map.get(nums[i]) > 1) {map.merge(nums[left], -1, Integer::sum);sum -= nums[left];left++;}// 3，更新maxSum = Math.max(maxSum, sum);}return maxSum;}
}
2958. 最多 K 个重复元素的最长子数组
思路【我】：
和上一题一模一样。只需要把while (map.get(nums[i]) > 1)改成while (map.get(nums[i]) > k)。
class Solution {public int maxSubarrayLength(int[] nums, int k) {int n = nums.length;int left = 0;int maxLen = 0;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {// 1，入map.merge(nums[i], 1, Integer::sum);// 2，出while (map.get(nums[i]) > k) {map.merge(nums[left], -1, Integer::sum);left++;}// 3，更新maxLen = Math.max(maxLen, i - left + 1);}return maxLen;}
}
2024. 考试的最大困扰度
思路【我】：
这题关键在于理解题意。题意：窗口内T或F的数量不能！同时！超过k（可以一方超过k）。
不定长滑动窗口三步曲：入–出–更新。
class Solution {public int maxConsecutiveAnswers(String answerKey, int k) {// 题意：窗口内T或F的数量不能！同时！超过k（可以一方超过k）char[] ch = answerKey.toCharArray();int n = ch.length;int t = 0;int f = 0;int left = 0;int maxLen = 0;for (int i = 0; i < n; i++) {// 1，入if (ch[i] == 'T') {t++;} else {f++;}// 2，出（仅在T和F同时超过k）while (t > k && f > k) {if (ch[left] == 'T') {t--;} else {f--;}left++;}// 3，更新maxLen = Math.max(maxLen, i - left + 1);}return maxLen;}
}