日升时奋斗，日落时自省
目录
一、长度最小的子数组
二、无重复字符的最长子串
三、最大连续1的个数III
四、将x减到0的最小操作数
五、水果成篮
六、找到字符串中所有字母异位词
七、串联所有单词的⼦串
八、最小覆盖子串
注：滑动窗口其实很类似与快慢指针，主要步骤入窗口 进行判断 出窗口
一、长度最小的子数组
题目来源：. - 力扣（LeetCode）
子数组：是数组中连续几个数（集合）
题目主要内容找到子数组个数最少的和满足target
代码：
public int minSubArrayLen(int target, int[] nums) {
//0x3f3f3f3f 表示Integer最大值的一半
int ret=0x3f3f3f3f, n=nums.length;
int sum=0;
for(int left = 0, right = 0;right<n;right++){
//入窗口
sum+=nums[right];
//判定出窗口条件
while(sum>=target){
//求最小长度
ret=Math.min(ret,right-left+1);
//出窗口
sum-=nums[left];
left++;
}
}
//如果值不变说明没有找到 就是 0 如果找到了用ret原值
return ret==0x3f3f3f3f?0:ret;
}二、无重复字符的最长子串
题目来源：. - 力扣（LeetCode）
题目主要内容找所有子串中不重复的最长子串且不重复
代码：
public int lengthOfLongestSubstring(String s) {
//将字符串转化为数组
char[] nums=s.toCharArray();
int n=nums.length;
//满足数字、符号、英文字母的ascll码
char[] hash=new char[128];
int left = 0, right = 0;
int ret=0;
while(right<n){
//入窗口
hash[nums[right]]++;
//条件判断
while(hash[nums[right]]>1){
//出窗口
hash[nums[left]]--;
left++;
}
//计算条件
ret=Math.max(ret,right-left+1);
//每次都会进行入窗口的 所以结尾right++
right++;
}
return ret;
}三、最大连续1的个数III
题目来源：. - 力扣（LeetCode）
题目主要内容就是 找到连续1最多的子数组，这里面可以把0变为1最多k次
代码：
public int longestOnes(int[] nums, int k) {
int ret = 0;
for(int left = 0 , right = 0 , count = 0; right < nums.length ; right++){
//记录 0 的个数 ，创造判定条件
//入窗口
if(nums[right]==0){
count++;
}
//判定条件
while(count>k){
//直到 0 位置 个数--
if(nums[left]==0){
count--;
}
left++;
}
//每次入窗口都会记录1的长度 并且 对比 取 最大值
ret=Math.max(ret,right-left+1);
}
return ret;
}四、将x减到0的最小操作数
题目来源：. - 力扣（LeetCode）
题目主要内容 每次 减 最左边 或者 最右边的值 目标值恰好减到 0
其实正面看 考虑的条件是很多的，不止四个需要判断的条件 （正难则反）
反向分析：
代码：
public int minOperations(int[] nums, int target) {
int left = 0 , right = 0, ret = -1;
int n=nums.length;
int sum=0;
//计算 总和
for(int x : nums){
sum+=x;
}
//求差值
int diff=sum-target;
//差值必须是存在的 如果都不存在了，直接返回结果
if(diff<0){
return -1;
}
//计算临时和
int tmp=0;
while(right<n){
//入窗口
tmp+=nums[right];
//条件判断
while(tmp>diff){
tmp-=nums[left];
left++;
}
//出窗口
if(tmp==diff){
ret=Math.max(ret,right-left+1);
}
right++;
}
//注意：这里求的是外面的最小个数 所以这里要那整个长度去减
return ret==-1?-1:nums.length-ret;
}五、水果成篮
题目来源：. - 力扣（LeetCode）
题目主要内容 水果承篮 一共有两个篮子 一个篮子只能放一种水果 计算能连续装最多个水果（仅限两种）
代码：
public int totalFruit(int[] fruits) {
int left =0;
int right =0;
int ret =0,count=0,n=fruits.length;
//计算种类
int kind =0;
//提供判断条件 计算当前水果种类的个数
int[] hash=new int[n];
while(right<n){
//入窗口
if(hash[fruits[right]]==0){
kind++;
}
hash[fruits[right]]++;
//条件判断
while(kind>2){
hash[fruits[left]]--;
//出窗口
if(hash[fruits[left]]==0){
kind--;
}
left++;
}
//每次入窗口都会进行一次计算
count=Math.max(count,right-left+1);
right++;
}
return count;
}六、找到字符串中所有字母异位词
题目来源：. - 力扣（LeetCode）
题目主要内容 就是在字符串找子串异位词
异位词：abc 的异位词 就是 bca、acb就是本身不变，但是位置变了
代码：
public List<Integer> findAnagrams(String ss, String pp) {
List<Integer> ret=new ArrayList<>();
char[] s=ss.toCharArray();
char[] p=pp.toCharArray();
//存储子串 用于判断条件
int[] hash2 = new int[26];
for(char tmp:p){
hash2[tmp-'a']++;
}
//作为判断条件推进
int[] hash1=new int[26];
int m=p.length;
for(int left=0,right=0,count=0;right<s.length;right++){
//s[right]-'a'就是想表示 字符串中的字符
hash1[s[right]-'a']++;
//入窗口
if(hash1[s[right]-'a']<=hash2[s[right]-'a'])count++;
//判定条件
while(right-left+1>m){
char out=s[left];
//出窗口
left++;
//如果字符串中在这个滑动区间不够 凑成子串count--
if(hash1[out-'a']--<=hash2[out-'a'])count--;
}
//count就是用来计算是否满足子串个数的
if(count==m){
ret.add(left);
}
}
return ret;
}七、串联所有单词的⼦串
题目来源：. - 力扣（LeetCode）
题目主要内容 s字符串中的子串有words数组中的所有子串并记录下当前子串的初始位置
代码：
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret=new ArrayList<>();
Map<String,Integer> hash=new HashMap<>();
//保存数组中单词的频次
for(String str:words)hash.put(str,hash.getOrDefault(str,0)+1);
int len =words[0].length(),m=words.length;
//执行次数
for(int i=0;i<len;i++){
Map<String,Integer> hash2=new HashMap<>();
//开始滑动 滑动单位就是 数组单个长度
for(int left = i,right = i,count=0;right + len<=s.length();right+=len){
//将字符串中按 数组单个长度 进行拆分
String in=s.substring(right,right+len);
//入窗口
hash2.put(in,hash2.getOrDefault(in,0)+1);
//判断是否是我们需要的 如果是那就进行加加
if(hash2.get(in)<=hash.getOrDefault(in,0))count++;
//判断条件 如果条件是大于说明 已经多了
if(right-left+1>m*len){
//出窗口
String out=s.substring(left,left+len);
if(hash2.get(out)<=hash.getOrDefault(out,0))count--;
//left滑动后移
hash2.put(out,hash2.get(out)-1);
left+=len;
}
//每次入窗口都查看是否满足条件
if(count==m)ret.add(left);
}
}
return ret;
}八、最小覆盖子串
题目来源：. - 力扣（LeetCode）
题目主要内容 在s字符串中找到最小子串且包含t子串中的所有字符
代码：
public String minWindow(String ss, String tt) {
char[] s=ss.toCharArray();
char[] t=tt.toCharArray();
//存放tt的所有字符串
int[] hash1=new int[128];
//表示字符串种类
int kind=0;
for(char ch : t)
{
//计算字符串种类
if(hash1[ch]++==0){
kind++;
}
}
//统计临时子串
int[] hash2=new int[128];
//满足条件的最小长度
int minlen=Integer.MAX_VALUE;
//这里采用字符串截取 需要保留最小子串的初始位置
int begin=-1;
for(int left = 0,right = 0,count=0;right<s.length;right++){
//入窗口
char in= s[right];
if(++hash2[in]==hash1[in])count++;
//判断条件
while(count==kind){
//若果当前个数小于上一个最小值 在进行计算
if(right-left+1<minlen){
//计算最小值
minlen=right-left+1;
//保存最小子串起始位置的下标
begin=left;
}
//出窗口
char out=s[left++];
if(hash2[out]--==hash1[out])count--;
}
}
return begin==-1?new String():ss.substring(begin,begin+minlen);
}
