滑动窗口总结

滑动窗口总结

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4

---

• 本题不需要记录每一种种类的具体数量，直接使用Set就可以
• 窗口内恒定必须符合要求，如本题就是必须包含不重复字符
• r指针右移用于寻找新的下一个字符
• l用于窗口不符合条件时不断右移直到符合

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int l = 0;
        int r = 0;
        int res = 0;
        while(r < s.length()){
            //不包含
            if(!set.contains(s.charAt(r))){
                set.add(s.charAt(r));
                res = Math.max(res,r-l+1);
                r++;
            }else{
                set.remove(s.charAt(l));
                l++;
            }
        }
        return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

lc 904.水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
1
2
3

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
1
2
3
4

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
1
2
3
4

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
1
2
3

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

---

• 记录每种水果的数量

• 使用Map进行记录

• 关键代码：map.put(fruits[r],map.getOrDefault(fruits[r], 0) + 1);

class Solution {
    public int totalFruit(int[] fruits) {
        //set + 滑动窗口
        Map<Integer,Integer> map = new HashMap<>();
        int l = 0, r = 0, count = 0;
        int res = 0;
        while(r < fruits.length){
            map.put(fruits[r],map.getOrDefault(fruits[r], 0) + 1);
            //窗口不满足，需要移动左边
            while(map.size() > 2){
                map.put(fruits[l],map.get(fruits[l]) - 1);
                if(map.get(fruits[l]) == 0){
                    map.remove(fruits[l]);
                }
                l++;
            }
            res = Math.max(res,r - l + 1);
            r++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

lc 76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
1
2

示例 2：

输入：s = "a", t = "a"
输出："a"
1
2

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
1
2
3
4

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗

class Solution {
    Map<Character,Integer> map_s = new HashMap<>();
    Map<Character,Integer> map_t = new HashMap<>();
    public String minWindow(String s, String t) {
        //滑动窗口 s的窗口必须满足包含了所有的t 使用Map
        //初始化map_t
        for(char c : t.toCharArray()){
            map_t.put(c , map_t.getOrDefault(c , 0) + 1);
        }
        int l = 0, r = 0;
        String res = "";
        int minLen = s.length() + 1;
        while(r < s.length()){
            char cr = s.charAt(r);
            map_s.put(cr,map_s.getOrDefault(cr , 0) + 1);
            while(isValid() && l <= r){
                if(r - l + 1 < minLen){
                    minLen = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                char cl = s.charAt(l);
                map_s.put(cl,map_s.getOrDefault(cl , 0) - 1);
                l++;
            }
            r++;
        }
        return res;
    }
    public boolean isValid(){
        //s中对应t的字母必须存在且大于等于数量
          for (Character key : map_t.keySet()) {  
            if(map_s.getOrDefault(key,0) < map_t.get(key)) return false;
        } 
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36