滑动窗口系列(不定长滑动窗口长度) 9/2
一、将x减到0的最小操作数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
题意：
给定一个数组nums和一个整数x；每次操作的时候，移除左边和右边的元素，使得移除元素之和=x
思路：
一般从两边移除元素，有两种思路；
1.逆向思维，在数组中找到一个滑动窗口，和为sum-x,结果就为num.length-滑动窗口的长度
2.正向思维，前缀和后缀；
代码：
逆向思维：
class Solution {
public int minOperations(int[] nums, int x) {
int total = 0;
for(int num:nums){
total+=num;
}
if(total<x)return -1;
int left=0;
int right=0;
int max=-1;
int sum=0;
while(right<nums.length){
sum+=nums[right];
while(sum>total-x){
sum-=nums[left];
left++;
}
if(sum==total-x){
max=Math.max(max,right-left+1);
}
right++;
}
return max==-1?-1:nums.length-max;
}
}正向思维：
二、最高频元素的频数（排序+滑动窗口）
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。
执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。
输入：nums = [1,2,4], k = 5 输出：3 解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。 4 是数组中最高频元素，频数是 3 。
思路：使用滑动窗口的思路(条件是操作数<=k)
当操作数>k之后，就要移动left；left需要移动到costK不大于k
while(costK>k){
costK-=nums[right]-nums[left];
left++;
}如果<k，移动right；移动right的时候，需要更新costK，costK=(nums[right]-nums[right-1])*(right-left);因为所有的数字都变成了nums[right-1]了，然后一共有right-left个数字；
costK+=(long)(nums[right]-nums[right-1])*(right-left);移动的过程中寻找最大值；
注意：costK的类型要是long，可能溢出
代码：
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int left=0;
int right=1;
int res=1;
long costK = 0;
while(right<nums.length){
costK+=(long)(nums[right]-nums[right-1])*(right-left);
while(costK>k){
costK-=nums[right]-nums[left];
left++;
}
res=Math.max(res,right-left+1);
right++;
}
return res;
}
}三、每种字符至少取K个
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
题意：
思路：逆向思维
题目中要求从左边或者右边取，将a\b\c三个字符取出最少K类，求最小的操作次数；
1.首先统计出字符串中字符的数目
2.然后减去k个，如果减去之后变为负数，返回-1
3.然后开始滑
逆向思维就是：题目中是否存在一段子串满足字符出现最多的次数为:count[0]-k,count[1]-k,count[2]-k。求出这段子串的最大长度
eg:"aabaaaacaabc" k=2 a:8 b:2 c:2
然后a\b\c最多出现的次数可以为:6,0,0; 每次遍历到一个字符，就将出现的次数-1(还可以出现多少次)，如果出现<0的情况，左边界就要改变了。
代码：
class Solution {
public int takeCharacters(String s, int k) {
if(k==0)return 0;
// 1.统计次数
int[] count=new int[3];
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
count[ch-'a']++;
}
// 2.将map中的字母-k
for(int i=0;i<3;i++){
if(count[i]<k)return -1;
count[i]-=k;
}
//滑动窗口正文
int left = 0;
int right = 0;
int res = 0;
while (right < s.length()) {
char ch = s.charAt(right);
count[ch-'a']--;
while (count[0] < 0 ||count[1] < 0 || count[2] < 0) {
char ch1 = s.charAt(left);
count[ch1-'a']++;
left++;
}
res = Math.max(res, right - left + 1);
right++;
}
return s.length() - res;
}
}四、找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
题意：
给定一个数组nums,求子数组中删除k个元素后，所有元素都相等，返回相同元素的最大个数。
思路：
滑动窗口左边界改变的的条件是：但滑动窗口中频率不是最大的数字的总和>k,就要移动左边界，直到总和<k;
while (right-left+1-maxFreq > k) {
int leftNum = nums.get(left);
map.put(leftNum, map.get(leftNum) - 1);
left++;
}每次更新map哈希表的时候，顺便获取到哈希表中出现频率最多的数字。
int num = nums.get(right);
map.put(num, map.getOrDefault(num, 0) + 1);
maxFreq=Math.max(maxFreq,map.get(num));代码：
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int left = 0;
int right = 0;
int maxFreq = 0;
int res = 1;
while (right < nums.size()) {
//遍历元素 将num统计到map中
int num = nums.get(right);
map.put(num, map.getOrDefault(num, 0) + 1);
maxFreq=Math.max(maxFreq,map.get(num));
//当滑动窗口中其他数字的次数>k时
while (right-left+1-maxFreq > k) {
int leftNum = nums.get(left);
map.put(leftNum, map.get(leftNum) - 1);
left++;
}
res=Math.max(right-left+1,res);
right++;
}
return maxFreq;
}
}