力扣1658.将x减到0点最小操作数
正难则反
想法永远是从暴力开始，然后观察能否使用滑动窗口优化
最后总长度-一个中间区域的最长
解法:滑动窗口
left=0,right=0
进窗口
判断
出窗口
更新结果
⚠️里面的值必须都是正的才能使用滑动窗口
class Solution { public int minOperations(int[] nums, int x) { int left=0; int right=0; int n=nums.length; int sum=0; for(int a:nums)sum+=a; int target=sum-x; int tmp=0; int len=-1; if(target<0)return-1; //我认为当前比较难的代码编写，就是很可能理解不出来两个循环的条件哪个在里面哪个在外面 //出窗口的在里面，入窗口的在外面 while(right<n){ tmp+=nums[right]; //进窗口 while(tmp>target){ //出窗口的条件 tmp-=nums[left]; left++; } if(tmp==target){ len=Math.max(len,right-left+1); } right++; } if(len==-1) return len; else return n-len; } }
力扣904.水果成篮
最后翻译题意，就是找最长的子数组，在这段子数组中最多有两种类型不同
法1:暴力解法+哈希表
法2:滑动窗口（判断right是否要回去)
解法1:模拟哈希表
class Solution { public int totalFruit(int[] fruits) { int left=0; int right=0; int count=0; //我们常常借助哈希表来去统计有没有重复的次数 int len=0; int n=fruits.length; //如果是字符集，可以使用这个来模拟,下标表示种类，数字表示个数 //模拟哈希表，因为他的长度在那里，为什么是n+1,因为可以不用去修改东西，0的下标就是1而不是0，因为最少也是一种。这样就可以使，假如fruit[right]==1，那么对应的t[1]，而且不用考虑太多，n+1是肯定够的 int []t=new int[n+1]; //统计窗口内水果的种类 // Map<Integer,Integer>hash=new HashMap<Integer,Integer>(); while(right<n){ //看你模拟的哈希表中，是否是0，假如是0就说明没有出现这个种类，那么种类就需要++ //count if(t[fruits[right]]==0){ count++;} t[fruits[right]]++; //出窗口 while(count>2){ t[fruits[left]]--; if(t[fruits[left]]==0){ count--; } left++; } //len，注意什么时候更新结果，是等于2的时候更新结果，假如放到前面，那么就变成等于三也去更新结果了。 len=Math.max(len,right-left+1); right++; } return len; } }
使用HashMap
class Solutionclass Solution { public int totalFruit(int[] fruits) { int left=0; int right=0; int count=0; //我们常常借助哈希表来去统计有没有重复的次数 int len=0; int n=fruits.length; //如果是字符集，可以使用这个来模拟,下标表示种类，数字表示个数 // int []t=new int[n+1]; //统计窗口内水果的种类 Map<Integer,Integer>hash=new HashMap<Integer,Integer>(); while(right<n){ //看你模拟的哈希表中，是否是0，假如是0就说明没有出现这个种类，那么种类就需要++ //count hash.put(fruits[right],hash.getOrDefault(fruits[right],0)+1); //包含的代码不会写 while(hash.size()>2){ //put也是改变的意思，不能光认为它是增加的含义 hash.put(fruits[left],hash.get(fruits[left])-1); if(hash.get(fruits[left])==0){ hash.remove(fruits[left]); } left++; } //len len=Math.max(len,right-left+1); right++; } return len; } }
力扣438.找到字符串中所有字母异位词(两种方法)
//如何判断两个字符是不是异位词
滑动窗口
两类题：
right不断变化，left常常不变，窗口的大小不固定
但是这个滑动窗口是固定的
法一：
补充知识点:字符串的charAt(i) 获取字符串
s.charAt(i),返回字符串第i个下标的值，
Arrays.equals(x1,x2);
class Solution { public static List<Integer> findAnagrams(String s, String p) { int left = 0; List<Integer> res = new ArrayList<>(); int m = p.length(); int right = 0; int[] sCnt = new int[26]; int[] pCnt = new int[26]; for (int i = 0; i < p.length(); i++) { //这个就是把p的字符，按照acil下标码顺序减去a存入（模拟的）哈希表里面。 pCnt[p.charAt(i) - 'a']++; } while (right <s.length()) { //这个就是把s的字符，按照acil下标码顺序减去a存入（模拟的）哈希表里面。 sCnt[s.charAt(right)-'a']++; if (right - left + 1 > m) { sCnt[s.charAt(left)-'a']--; left++; } //看两个数组是否相同， if(right-left+1==m&&Arrays.equals(sCnt,pCnt)){ res.add(left); } right++; } return res; } }
法二：
他是通过count 来判断符不符合条件
他的想法：
开始和法1相同，都是模拟哈希，然后把要去重的存起来，然后把遍历s
//这个的意思是，pCnt是我们要的，那么sCnt就是要看它里面有没有和pCnt一样的，而且一个要点，他的字符串可以任意顺序，所以我们假如sCnt咩有pCnt里面那个东西，那么count不更改，假如有，但是大于他，就说明多了，count也不会++，就像是一个蛋糕，他先给你准备壳，你照着壳来做蛋糕if(sCnt[s.charAt(right)-'a']<=pCnt[s.charAt(right)-'a'])
count++;
第二块
if(sCnt[s.charAt(left)-'a']<=pCnt[s.charAt(left)-'a']){
count--;}这个是说假如你去除的是一个必要的，那么就说明这一段不是，但是count会减一次，他就像是统计必要的这三个字母，你假如少了一个，那么count就--
public static List<Integer> findAnagrams(String s, String p) { int left = 0; List<Integer> res = new ArrayList<>(); int m = p.length(); int right = 0; int[] sCnt = new int[26]; int[] pCnt = new int[26]; int count=0; for (int i = 0; i < p.length(); i++) { pCnt[p.charAt(i) - 'a']++; } while (right <s.length()) { sCnt[s.charAt(right)-'a']++; if(sCnt[s.charAt(right)-'a']<=pCnt[s.charAt(right)-'a']) count++; if (right - left + 1 > m) { if(sCnt[s.charAt(left)-'a']<=pCnt[s.charAt(left)-'a']){ count--;} sCnt[s.charAt(left)-'a']--; left++; } if(count==m){ res.add(left); } right++; } return res; }
