当前位置：首页 > news >正文

【算法】【优选算法】滑动窗口（下）

news 2024/11/7 9:32:44

一、904.⽔果成篮

题目链接：904.⽔果成篮
题目描述：

题目解析：

这道题给的题目挺长，但是简化后就是给你一个数组，在其中找到数组元素只有两个数的最长子串。
提示中写了数组元素的范围是小于等于数组长度的。

1.1 滑动窗口

解题思路：

当我们遍历数组的时候，我们要让子数组中元素种类变多，就让子数组尾向后走；
让子数组中元素种类变少，就让子数组头向后走；这又是同向双指针问题。
我们还要使用一个计数器来标记子数组中的元素种类个数。
使用一个type数组来标记子数组中两个种类中的个数，以便后面对计数器操作。
进窗口：当元素种类个数小于等于2的时候，就让type数组中fruits[right]下标的元素加一，并让right向后走，这里面要注意如果是第一次进type数组，要让计数器加一。
出窗口条件：当计数器大于2的时候就出窗口。
出窗口：每次让type数组中的fruits[left]下标的元素加一，并让left向后走，这里面要注意如果是fruits[left]下标对应type数组元素为0，要让计数器减一。
更新结果：在出完窗口后的子数组一定是符合条件的，直接去原结果和子数组长度的较大值即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(n)
import java.util.*;
class Solution {public int totalFruit(int[] fruits) {int len = fruits.length;int[] type = new int[len]; int ret = 0;int flag = 0;for(int left = 0, right = 0; right < len; right++) {if(flag <= 2) {if(type[fruits[right]] == 0) {flag++;  } type[fruits[right]]++ ;//进窗口}while(flag > 2) {//出窗口条件//出窗口type[fruits[left]]--;if( type[fruits[left]] == 0) flag--;left++;}ret = Math.max(ret,right - left + 1);//更新结果}return ret;}
}

1.2 暴力枚举

解题思路：

使用两层for循环将每一个符合要求的子数组都枚举出来。
我们也要使用一个计数器来标记子数组中的元素种类个数。
使用一个type数组来标记子数组中两个种类中的个数，以便后面对计数器操作。
这里面有细节处理问题：我们出第二层循环的时候有两种可能：
- 我们数组遍历完了，并且计数器小于等于2，出循环这时的[ i, j ]都是符合要求的。
- 我们计数器大于二出循环，这时只有[ i, j )是符合要求的（也就是j下标执向的是第三种类型的元素）。
会超时。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(n)
import java.util.*;
class Solution {public int totalFruit(int[] fruits) {int len = fruits.length;int ret = 0;for(int i = 0; i < len; i++) {int[] type = new int[len];int flag = 0;for(int j = i; j < len; j++) {if(flag <= 2) {if(type[fruits[j]] == 0) flag++;type[fruits[j]]++;}if(j == len - 1 && flag <= 2) {ret = Math.max(ret,j-i+1);break;}if(flag > 2) {ret = Math.max(ret,j-i);break;}}}    return ret;}
}

二、438.找到字符串中所有字⺟异位词

题目链接：438.找到字符串中所有字⺟异位词
题目描述：

题目解析：

字母异位词：其实就是将字符串中所有字母随机排序能构成的所有子串都互为异位词，如abc的异位词就有：abc，acb，bac，bca，cab，cba。
这道题就是让我们求给出字符串s中子串，是字符串p的异位词的首字母下标构成的集合。
两个字符串是不是异位词的判定方法：
- 将两个字符串排序，然后遍历一一比较。Java提供的sort时间复杂度O(NlogN)。
- 哈希原理：使用数组分别记录下字符串中每个字符的个数，比较数组是否相等即可。

2.1 滑动窗口

解题思路：
-当我们遍历字符串的时候，在保持子串的元素尽可能少的变化（进出字符的时候中间的字符不会变化），要让子串的长度变大，就让子串尾向后走，让子串的长度变小，就让子串头向后走，同向双指针。

记录下p字符串的长度lenP，一个数组hash1记录每个字符个数。
一个数组hash2记录当前子串每个字符个数。
进窗口：当子串长度小于lenP的时候，进字符。
出窗口条件：当子串长度不小于lenP的时候。
出窗口：让left下标对应字符出数组（也就是hash2对应下标减1）。
修改结果：在每次出窗口后都要看现在的子串长度是否等于lenP，和两个数组是否一样。一样就将当前的left进入结果数组。
上述的思路最后由于我们需要比较数组所以我们的复杂度虽然是O(N)但是，每一次比较都有26次。我们可以使用下述优化方案：
- 我们使用一个计数器，来统计有效字符的个数（也就是与p字符串中字符相同的，子串中字符个数）。
- 当我们进窗口之后，当前hash2数组right下标的个数小于等于hash1中的值时，就计数器加1。
- 当出窗口之前，当前hash2数组left下标的个数小于等于hash1中的值时,就计算器减1。
- 最后只需要比较计数器与p的长度比较即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
import java.util.*;
class Solution {public List<Integer> findAnagrams(String s, String p) {char[] ss = s.toCharArray();char[] pp = p.toCharArray();List<Integer> ret = new ArrayList<>();int[] hash1 = new int['z' - 'a' + 1];int lenP = p.length();int lenS = s.length();for(int i = 0; i < lenP; i++)hash1[pp[i]-'a']++;int[] hash2 = new int['z' - 'a' + 1];for(int left = 0,right = 0; right < lenS; right++) {//进窗口hash2[ss[right] - 'a']++;if(right-left+1 > lenP) {//出窗口条件//出窗口hash2[ss[left] - 'a']--;left++;}//更新结果if( right-left + 1 == lenP) {if(Arrays.equals(hash1,hash2)) ret.add(left);} }return ret;}
}优化：
//时间复杂度：O(n)
//空间复杂度：O(1)
import java.util.*;
class Solution {public List<Integer> findAnagrams(String s, String p) {char[] ss = s.toCharArray();char[] pp = p.toCharArray();List<Integer> ret = new ArrayList<>();int[] hash1 = new int['z' - 'a' + 1];int lenP = p.length();int lenS = s.length();for(int i = 0; i < lenP; i++)hash1[pp[i]-'a']++;int[] hash2 = new int['z' - 'a' + 1];int count = 0;for(int left = 0,right = 0; right < lenS; right++) {//进窗口hash2[ss[right] - 'a']++;if(hash2[ss[right] - 'a'] <= hash1[ss[right] - 'a']) count++;if(right-left+1 > lenP) {//出窗口条件//出窗口if(hash2[ss[left] - 'a'] <= hash1[ss[left] - 'a']) count--;hash2[ss[left] - 'a']--;left++;}//更新结果if( right-left + 1 == lenP) {if(count == lenP) ret.add(left);} }return ret;}
}

2.2 暴力枚举

解题思路：

记录下p字符串的长度lenP，一个数组hash1记录每个字符个数。
使用两层for循环，使用数组hash2记录下每次长度为lenP的子串的每个字符个数。
比较两个数组，相等记录子串首元素下标。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
import java.util.*;
class Solution {public List<Integer> findAnagrams(String s, String p) {char[] ss = s.toCharArray();char[] pp = p.toCharArray();List<Integer> ret = new ArrayList<>();int[] hash1 = new int['z' - 'a' + 1];int lenP = p.length();int lenS = s.length();for(int i = 0; i < lenP; i++)hash1[pp[i]-'a']++;for(int i = 0; i < lenS; i++) {int[] hash2 = new int['z' - 'a' + 1];for(int j = i; j < i + lenP; j++) {if(j >= lenS) break;hash2[ss[j]-'a']++;}if(Arrays.equals(hash1,hash2)) ret.add(i);}return ret;}
}

三、30.串联所有单词的⼦串

题目链接：30.串联所有单词的⼦串
题目描述：

题目解析：

由于我们的words数组中每一个字符串的长度都是一样的，所以这道题跟上一道题其实是一道题。

3.1 滑动窗口

解题思路：

我们的解题思路跟上一道题是一样的，只不过这次要是有真正的容器HashMap来表示了。
我们两个指针每次走的长度也是words[0]字符串的长度。
窗口循环次数，也要变，我们需要循环words中字符串的长度次数，因为当我们循环了这么多次后，再次循环就跟第一次重复了。例如在words[0].length() == 2的时候，第一次使用窗口是每两个字母为一组，当第三次使用时其实就是将第一次分组后的第一个组除去剩下的。

题目代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
import java.util.*;
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();int len = words[0].length();HashMap<String,Integer> hash1 = new HashMap<>();for(String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);for(int i = 0; i <len; i++) {HashMap<String,Integer> hash2 = new HashMap<>();for(int left = i, right = i, count = 0; right <= s.length()-len; right += len) {//进窗口String in = s.substring(right,right+len);hash2.put(in,hash2.getOrDefault(in,0)+1);if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;//出窗口条件if((right - left) / len + 1 > words.length) {//出窗口String out = s.substring(left,left+len);if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;hash2.put(out,hash2.get(out)-1);left += len;}if(count == words.length) ret.add(left);}}return ret;}
}

3.2 暴力枚举

解题思路：

直接两层for循环即可，只不过第一层是遍历每一个字母，第二层是一组一组遍历（即每次走的长度不一样）。
虽然时间复杂度也是O(n^2)，但这个是真的NN，上面的滑动窗口是mN比这个小太多了,所以会超时。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
import java.util.*
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();int len = words[0].length();HashMap<String,Integer> hash1 = new HashMap<>();for(String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);for(int i = 0; i < s.length(); i++) {HashMap<String,Integer> hash2 = new HashMap<>();for(int j = i; j+len <= s.length(); j += len) {String in = s.substring(j,j+len);hash2.put(in,hash2.getOrDefault(in,0)+1);if(hash1.equals(hash2)) ret.add(i);}}return ret;}
}

四、76.最⼩覆盖⼦串

题目链接：76.最⼩覆盖⼦串
题目描述：

题目解析：

这道题就是求在s字符串中的子串包含t中所有字符（个数也要一样）的最小子串。

4.1 滑动窗口

解题思路：

其实这道题还是和第二题有异曲同工之妙。
只需要使用两个hash表来记录个数即可，hash1记录t字符串中的每种字符的个数。
hash2记录[left，right]区间中的每种字符个数。
使用count计数器来记录有效字符个数。
进窗口：每个right的元素直接进窗口，进了窗口后判断当前字符是不是有效字符。
出窗口条件：count计数器中有效字符大于等于t字符串长度。
出窗口：出left元素，在出元素之前，判断出的元素是否是有效元素。
更新结果：由于是要返回字符串，所以我们记录字符串的头尾下标，由于出窗口是要让count小于t长度，所以我们要在出窗口前更新结果。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
import java.util.*
class Solution {public String minWindow(String ss, String tt) {char[] s = ss.toCharArray();char[] t = tt.toCharArray();int[] hash1 = new int[128];for(char ch : t) {hash1[ch]++;}int[] hash2 = new int[128]; int count = 0;int retLeft = 0;int retRight = 0x3f3f3f3f;for(int left = 0, right = 0; right < s.length; right++) {//进窗口hash2[s[right]]++;if(hash2[s[right]] <= hash1[s[right]]) count++;//出窗口条件while(count >= t.length) {if(count == t.length) {if(right - left <= retRight - retLeft) {retLeft = left;retRight = right;}}//出窗口if(hash2[s[left]] <= hash1[s[left]]) count--;hash2[s[left]]--;left++;}// System.out.println(count+" "+ t.length);} if(retRight == 0x3f3f3f3f) {return "";} else {return ss.substring(retLeft,retRight+1);}}
}

4.2 暴力枚举

解题思路：

直接使用两层for循环将每一种使count计数器等于t.length的结果（即s字符串中的子串包含t中所有字符）枚举出来即可。
会超时。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
import java.util.*
class Solution {public String minWindow(String ss, String tt) {char[] s = ss.toCharArray();char[] t = tt.toCharArray();int[] hash1 = new int[128];for(char ch : t) {hash1[ch]++;}int retLeft = 0;int retRight = 0x3f3f3f3f;for(int i = 0; i < s.length; i++) {int[] hash2 = new int[128]; int count = 0;for(int j = i; j < s.length; j++) {hash2[s[j]]++;if(hash2[s[j]] <= hash1[s[j]]) count++;if(count == t.length) {if(j-i < retRight-retLeft) {retLeft =i;retRight = j;}break;}}}if(retRight == 0x3f3f3f3f) {return "";} else {return ss.substring(retLeft,retRight+1);}}
}