需要重点关注的题目

剑指 Offer 57 - II. 和为s的连续正数序列

• 第一次复习：严重遗忘
• 第二次复习：做出来了，先检验是否构成答案，然后判断是移动左窗口还是右窗口。

3. 无重复字符的最长子串

• 第一次复习：严重遗忘，不会做了。
  • 和其他一题的答案记串了，这题是移动左指针从map中拿走元素。
• 第二次复习：做出来了，比较熟练了。典型的求最大窗口。
• 第三次复习：秒

424. 替换后的最长重复字符

• 第一次复习：基本套路还记得，摸索了一会就复原了，比较熟悉的做出来了。
• 第二次复习：秒

76. 最小覆盖子串

• 第一次复习：有些遗忘，出了个小bug，在摸索之下还是写出来了，下次要重点复习。
• 第二次复习：秒

930. 和相同的二元子数组

• 第一次复习：严重遗忘，不会做了。
  • 维护两个滑窗，一个找最左边使窗口满足或不满足条件的，另一个找最左边使窗口不满足条件的。

340. 至多包含 K 个不同字符的最长子串

• 第一次复习：熟练解出来了。

• 第二次复习：秒

  算法出现的标记

• 最长子串

• 子数组
• 给你两个字符串基本上就是滑窗了

解题框架

最大窗口

每次更新窗口长度最值。例如，3，159，340

// 以 340 题 为例子
while (r < s.length()){
    // 将新的r加入滑动窗口信息表
    map.pur(s.charAt(r), r);
    // 检查窗口是否合法，若不合法，更新左边界直至窗口合法
    if (map.size() > k){
        int deleteIndex = Collections.min(map.values());
        map.remove(s.charAt(deleteIndex);
        l = deleteIndex+1;
    }
    // 到这一步的时候，窗口一定合法，更新最大长度
    ret = Math.max(ret, r - l + 1);
    // 每次r向右移一步
    r++;
}
return ret;

最小窗口

以209. 长度最小的子数组为例子

while (r < nums.length){
    // 先将新的r加入窗口
    sum += nums[r++];
    // 判断窗口是否valid，如果valid，向右移动left并且同时更新窗口最小值 直至不合法为止
    while (sum >= target){
        ret = Math.min(ret, r - l);
        sum -= nums[l++];
    }
}
return ret;

定长窗口

以 567. 字符串的排列 为例子

// 检测第一个窗口
if (equals(temp, counter)) return true;
// 检测剩下的窗口
for (int i = s1.length(); i < s2.length(); i++){
    // 窗口整体向右平移一步
    // 移除之前左边的元素
    temp[s2.charAt(i - s1.length()) - 'a']--;
    // 加入新的右边的元素
    temp[s2.charAt(i) - 'a']++;
    // 检测新出的窗口
    if (equals(temp, counter)) return true;
}
// 返回结果

贪心寻找最大窗口

返回最后的r-l，不会更新窗口长度最值。例如，424，1004

while (r < s.length()){
    counter[s.charAt(r)-'a']++;
    maxCount = Math.max(maxCount, counter[s.charAt(r)-'a'];
    // update left
    if (r - l + 1 - maxCount > k){
        // 新出来的窗口invalid，大小-1
        l++;
    }
    r++;
}
return r - l;

题型

求所有符合条件的窗口

剑指 Offer 57 - II. 和为s的连续正数序列

• 这题好难啊，自己写了半小时没出来。
• 答案
  • 循环条件为 while (l < r)
    • 先检查sum==target
    • 然后若sum >= target, sum -= l++
    • 然后若sum < target, sum += ++r

930. 和相同的二元子数组*

新的题型
答案：

• 对于每个right结尾的窗口
• 我们算出最左边的可以使窗口valid以及最左边的使窗口invalid的两个指针

• 他们相减就是，以right结尾的窗帘的valid的总数。

  public int numSubarraysWithSum(int[] nums, int goal) {
    int l1 = 0, l2 = 0, r = 0;
    int sum1 = 0, sum2 = 0;
    int ret = 0;
  
    while (r < nums.length){
        sum1 += nums[r];
        // left most could make an valid window
        while (l1 <= r && sum1 > goal){
            sum1 -= nums[l1++];
        }
        // left most that makes the window invalid
        sum2 += nums[r];
        while (l2 <= r && sum2 >= goal){
            sum2 -= nums[l2++];
        }
        ret += l2 - l1;
        r++;
    }
  
    return ret;
  }
  

  求最大窗口

  395. 至少有 K 个重复字符的最长子串

  题解
  答案：

• 对k个字符做枚举，就是说，

  • 有1个重复字符的最长子串
  • 有2个重复字符的最长子串
  • 有3个重复字符的最长子串
  • …
  • 有k个重复字符的最长子串
• 然后去最大值，就是答案。
• 计算每个k个重复字符的最长子串的时候，我们使用滑动窗口求最大值
• 
  

3. 无重复字符的最长子串（Done）

• 先更新左边界，在更新右边界
• 如何更新左边界是我卡住的地方 ```java // Option 1: // update l until the window is valid int deleteIndex = map.get(s.charAt(r)); while (l <= deleteIndex){ map.remove(s.charAt(l++)); }

// Option 2: // 如果不从map中删除，则重复元素可能不在窗口内，所以通过max来消除这个情况。
l = Math.max(l, map.get(s.charAt(r)) + 1); ```

159. 至多包含两个不同字符的最长子串（Done）

掌握程度：熟悉

答案：

• 记录一个map<字符，最后出现的索引>
• 循环内 while (r < nums.length)
  • 先更新map中字符最后出现的索引
  • 检查是否需要更新左边界
    • 找出map中最左边的索引->最小的索引 = Collections.min(map.values());
    • 删除map中该索引对应的字符
    • 新的left = 最小的索引 + 1 【完全移除了一个元素】
  • 更新ret = Math.max(ret, r - l + 1)
• 返回 ret

  340. 至多包含 K 个不同字符的最长子串（Done）

  同159题

  1208. 尽可能使字符串相等 （Done）

  同159套路，根据条件更新左边界直到窗口valid。

424. 替换后的最长重复字符（Done）

掌握程度：熟悉

这道题目是特例，好好记一下
答案：

• 记录某个窗口中出现过的历史最多的重复元素
• 循环内 while (r < nums.length)
  • 先把新的r更新一下counter
  • 计算一下新的历史最多重复的元素
  • 判断目前新的窗口是否valid
    • 若不，则left++，
  • r++ 尝试向右边扩大
• 结果r - l；

求最小窗口

76. 最小覆盖子串（Done）

• 先更新右指针，再循环更新左指针并且更新最小窗口

209. 长度最小的子数组（Done）

• 先更新右指针，再循环更新左指针并且更新最小窗口，直到invliad

求固定大小的窗口

使用left指针和长度即可，每次右移一步，至于是移动前还是移动后判断都行

438. 找到字符串中所有字母异位词 （Done）

• 难点在于终止条件
• 答案
  • 先把窗口扩大至k
  • while循环 终止与窗口再向右移(r+1)就出界了 while (r+1 < s.length())
    • 先看看这个窗口满足条件么
    • 窗口向右平移一格
  • 循环结束后，检查最后一个窗口，没被检查到，因为再右移就出界了
  • 返回结果

239. 滑动窗口最大值 (Done)

• 双端队列
• 慢慢滑动窗口

567. 字符串的排列(Done)