基本思想
利用两个指针i, j，始终保持区间[i, j]时符合题目条件的区间
最长子数组模板 1.当不满足条件时，拓展右边界，当满足条件时，缩短左边界，最后得到一个解并暂存
2.循环第一步，又得到一个解，将其与第一个解相对比，得到最优解并暂存，以此类推。
for(枚举选择)右边界while(不符合条件)左边界更新结果
算法小抄模板(c++)
/* 滑动窗口算法框架 */void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0;while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}}
904.水果成篮
本题的题意就是找到一个区间[i, j]，使区间内的元素只有两种
使用外层循环遍历数组，内层循环保证区间符合题意，这样我们就能得到以所有i结尾的符合题意的最大区间
细节
如何处理“不符合条件”？
本题中符合条件指窗口中水果种类是2。 用HashMap记录，Map<水果种类，出现频次>， 延伸右边界时，增加频次。缩进左边界时，减少频次。 频次为0时，从map删除。 map的大小为2时，正好符合条件。
class Solution {
public int totalFruit(int[] tree) {
//处理特殊情况
if (tree == null || tree.length == 0) return 0;
int n = tree.length;
Map<Integer, Integer> map = new HashMap<>();
int maxLen = 0, left = 0;
for (int i = 0; i < n; i++) {
//getOrDefault() 方法获取指定 key 对应对 value
map.put(tree[i], map.getOrDefault(tree[i], 0) + 1); // 右边界
while (map.size() > 2) { // 不符合条件：水果种类大于2
map.put(tree[left], map.get(tree[left]) - 1);
if (map.get(tree[left]) == 0) map.remove(tree[left]);
left++; // 左边界
}
maxLen = Math.max(maxLen, i - left + 1); // 更新结果
}
return maxLen;
}
}
76. 最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<Character, Integer>();
HashMap<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0;
// 记录最小覆盖字串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 判断取出的字符是否在字串中
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c,0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断是否需要收缩（已经找到合适的覆盖串）
while (valid == need.size()) {
//在这里返回结果
if (right - left < len) {
start = left;
len = right - left;
}
char c1 = s.charAt(left);
left++;
//更新的数据
if (need.containsKey(c1)) {
if (window.get(c1).equals(need.get(c1))) {
valid--;
}
window.put(c1, window.getOrDefault(c1, 0) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
模板
Java模板
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character ,Integer> need=new HashMap<>();
HashMap<Character,Integer> window=new HashMap<>();
//把s1送入need
for (char c : s1.toCharArray()) {
need.put(c,need.getOrDefault(c,0)+1);
}
int left = 0;
int right = 0;
int valid = 0;//判定是否元素齐全
while (right < s2.length()){
char c = s2.charAt(right);
right++;
// 进行窗口内数据的一系列更新
/**
if (need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if (window.get(c).equals(need.get(c))){
valid++;
}
}
*/
//判断窗口是否收缩
while (right-left>s1.length()/){/这里是判断啥时候伸缩的条件 每题不一样
/**
//在这里更新结果 在这里判断是否找到合法字符串
if (valid == need.size()){
return true;
}
*/
char c1 = s2.charAt(left);
left++;
//进行窗口内数据的更新
/**
if (need.containsKey(c1)){
if (window.get(c1).equals(need.get(c1))) {
valid--;
}
window.put(c1, window.getOrDefault(c1, 1) - 1);
}
*/
}
}
return false;
}
}
套模板的答案
class Solution {
public String minWindow(String s, String t) {
//定义一个数组存放存放目标数组中每个元素出现的次数
HashMap<Character, Integer> need = new HashMap<>();
//窗口中每个元素出现的次数
HashMap<Character, Integer> window = new HashMap<>();
//遍历目标字符串每一个元素,记录出现的次数,存入need哈希数组中
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0;
int right = 0;
int valid = 0;//valid 变量表示窗口中满足 need 条件的字符个数
// 记录最小覆盖字串的起始索引及长度
int start = 0;
int len = Integer.MAX_VALUE;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
//如果一个字符进入窗口，应该增加 window 计数器；
// 判断取出的字符是否在字串中
if (need.containsKey(c)) {//如果我们在窗口中移入的元素c包含在need数组内
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {//valid变量满足need条件
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {//已经找到合适的覆盖串
if (right - left < len) {
start = left;
len = right - left;
}
// // d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 1) - 1);
}
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
}
}
567. 字符串的排列
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character ,Integer> need=new HashMap<>();
HashMap<Character,Integer> window=new HashMap<>();
//把s1送入need
for (char c : s1.toCharArray()) {
need.put(c,need.getOrDefault(c,0)+1);
}
int left = 0;
int right = 0;
int valid = 0;//判定是否元素齐全
while (right < s2.length()){
char c = s2.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if (window.get(c).equals(need.get(c))){
valid++;
}
}
//判断窗口是否收缩
while (right-left>s1.length()){
//在这里判断是否找到合法字符串
if (valid == need.size()){
return true;
}
char c1 = s2.charAt(left);
left++;
//进行窗口内数据的更新
if (need.containsKey(c1)){
if (window.get(c1).equals(need.get(c1))) {
valid--;
}
window.put(c1, window.getOrDefault(c1, 1) - 1);
}
}
}
return false;
}
}
阶段总结一下
通过这个模板做的这两题,我们需要思考的地方有以下:
- 右边界进行扩张的时候需要更新什么数据呢?
一般情况 窗口中新加进来的元素与need表进行比较看看是否相同,如果相同我们要进行window窗口的更新在c++中比较容易理解window[]++,这个在Java中表述为 window.put(c,window.getOrDefault(c,0)+1); 同时的我们维护的valid变量也要进行更新,因为这个变量是记录我们窗口中的元素的个数种类的然后用valid==need.size()来确定是否已经找到完备目标元素 如果need.containsKey(c1) 并且window.get(c1).equals(need.get(c1))则valid++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);//包含它
if (window.get(c).equals(need.get(c))){//包含的数量也相等
valid++;
}
}
- 左边界在收缩时候要更新什么数据呢?
一般 与右边界是对称的,如果need.containsKey(c1) 并且window.get(c1).equals(need.get(c1))则valid— 如果need.containsKey(c1)则window.put(c1, window.getOrDefault(c1, 1) - 1);相当于c++的window[]—
//进行窗口内数据的更新
if (need.containsKey(c1)){
if (window.get(c1).equals(need.get(c1))) {
valid--;
}
window.put(c1, window.getOrDefault(c1, 1) - 1);
}
左边界收缩的条件是什么呢?
这个只能因题而论 就在left那个while里面写条件
我们需要的结果是要在哪里进行返回运算的呢?
因题而论
438. 找到字符串中所有字母异位词
套模板真香
class Solution04 {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character , Integer> window = new HashMap<>();
int left = 0;
int right = 0;
int valid = 0;
List<Integer> res = new ArrayList<>();
for (char c : p.toCharArray()) {
need.put(c,need.getOrDefault(c,0)+1);
}
while (right< s.length()){
char c = s.charAt(right);
right++;
//窗口内的更新
if (need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);//包含它
if (window.get(c).equals(need.get(c))){//包含的数量也相等
valid++;
}
}
//判断什么条件下left开始收缩
while (right - left >= p.length()){
//更新结果
if (valid == need.size()){
res.add(left);
}
char d = s.charAt(left);
left++;
//窗口内的更新
if (need.containsKey(d)){
if (window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.getOrDefault(d,0)+1);
}
}
}
return res;
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int left = 0;
int right = 0;
int rest = 0;
while (right<s.length()){
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c,window.getOrDefault(c,0)+1);
// 判断左侧窗口是否要收缩
while (window.get(c)>1){
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d,window.getOrDefault(d,0)-1);
}
// 在这里更新答案
rest = Math.max(rest,right - left);
}
return rest;
}
}
此题中因为没有两个字符串,我们没有在模板中使用need以及valid因为这两个是设计两个字符串时的
更新窗口内数据也只需要简单的更新计数器window即可。
当window[c]值用Java就是window.get(c)大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动left缩小窗口了嘛。
在哪里更新结果res呢? 我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？
这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。
若有收获，就点个赞吧
0 人点赞
