1 滑动窗口理论基础

1.1 算法思想

一个固定大小的窗口在数据序列上滑动，并在窗口内执行特定操作的问题。

通俗的讲就是，对于数组，维持一个特定窗口/动态可变窗口，通过该窗口来在数组或者字符串上进行操作。

字面意思上理解：

滑动 ： 窗口时移动的，就是按照一定方向来进行移动

窗口：窗口大小并不是固定的，而是不断扩容直到满足一定条件；也可以不断缩小，找到满足条件的最小窗口；也可以固定大小。

1.2 使用场景

  • 满足xx条件（计算结果，出现次数，同时包含）
  • 最长/最短
  • 子串/子数组/子序列

感觉是你认为需要在一个数组/字符串中维持一个滑动的窗口来解题的题，都可以用滑动窗口来解决。

1.3 使用思路

寻找最长

核心：左右双指针(l.r)，$[l,r]$即为窗口内的元素。r为窗口的结束位置，l为窗口的起始位置。

每次滑动过程中：窗内元素满足条件，r向右移动扩大窗口，更新最优结果；窗内元素不满足条件，L向右移动缩小窗口。

模板如下：

1
2
3
4
5
6
7
8
int l = 0; // 窗内的起始位置
for(int r = 0;r<n;r++){ // 窗口的终止位置
	while(窗内元素不满足条件){
		窗口缩小：移除l对应的元素，l右移
	}
	更新最优结果到bestResult中;
}
return bestResult

寻找最短

核心：左右双指针(l.r)，$[l,r]$即为窗口内的元素。r为窗口的结束位置，l为窗口的起始位置。

每次滑动过程中：窗内元素不满足条件，r向右移动扩大窗口；窗内元素满足条件，L向右移动缩小窗口，更新最优结果。

模板如下

1
2
3
4
5
6
7
8
int l = 0; // 窗内的起始位置
for(int r = 0;r<n;r++){ // 窗口的终止位置
	while(窗内元素满足条件){
         更新最优结果bestResult // 因为要找最短的，所以满足条件后还需要窗口缩小，寻找到最短的最优结果
		窗口缩小：移除l对应的元素，l右移
	}
}
return bestResult

实现滑动窗口时，需要确定如下几点

  • 窗口内是什么
  • 如何移动窗口的起始位置
  • 如何移动窗口的结束位置

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

窗口内：满足和>=s的长度最小的连续子数组

起始位置如何移动：如果当前窗口值>=s，窗口需要缩小

1
2
3
4
5
6
7
8
for (int r = 0; r < n; r++) { // 枚举右端点
    ans += nums[r];
    while (ans >= target) { // 需要缩短子数组的长度，找到最短的子数组
        res = Math.min(res, r - l + 1);
        ans -= nums[l];
        l++;
    }
}

结束位置如何移动：结束位置就是遍历数组的指针，也就是for循环的索引

2 209.长度最小的子数组

209. 长度最小的子数组

中等

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

2.1 题目分析

可以暴力求解，但是时间复杂度市$O(n^2)$。这里可以使用滑动窗口来求解。

滑动窗口是一种处理数组子区间问题的有效方法，它的核心思想是通过两个指针 l 和 r 来表示一个窗口，这个窗口内的数值总和是我们关心的属性。

2.2 算法步骤

  1. 初始化：定义两个指针 l 和 r，分别代表窗口的左右边界，初始时都指向数组的开始位置。定义 ans 来存储当前窗口的和，res 用来存储满足条件的最短子数组的长度，初始值设为 Integer.MAX_VALUE，表示一个很大的数。
  2. 窗口扩张：遍历数组，每次将 r 指针向右移动一位，并将 nums[r] 加到 ans 中。这样，ans 就代表了从 l 到 r 的窗口内所有元素的和。
  3. 窗口缩小：如果 ans 大于等于 target，说明当前窗口内的和已经满足或超过了目标值，此时尝试缩小窗口以找到更短的子数组。将 l 指针向右移动一位，并将 nums[l] 从 ans 中减去，这样 ans 就代表了从 l+1 到 r 的窗口内所有元素的和。
  4. 更新结果：每次窗口缩小后，如果 ans 仍然大于等于 target，则更新 res 的值，取 r-l+1 和 res 中的较小值作为新的 res。
  5. 循环结束：重复步骤 2 和 3，直到 r 指针遍历完整个数组。
  6. 返回结果：如果 res 仍然是 Integer.MAX_VALUE，说明没有找到满足条件的子数组，返回 0；否则返回 res。

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int l = 0, ans = 0, res = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) { // 枚举右端点
            ans += nums[r];
            while (ans >= target) { // 需要缩短子数组的长度，找到最短的子数组
                res = Math.min(res, r - l + 1);
                ans -= nums[l];
                l++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

2.4 时间复杂度

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。这是因为每个元素最多被访问两次（一次是窗口扩张，一次是窗口缩小）。
  • 空间复杂度：O(1)，除了输入数组外，我们只需要常数级别的额外空间。

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

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

中等

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

3.1 题目分析

滑动窗口的方法来解决。滑动窗口在这里指的是一个动态的子串区间，这个区间内的字符都是唯一的。

窗口内需要满足的条件：窗口内的字符必须是唯一的。所以可以用一个hashset来记录窗口内出现的字符，确保唯一性。

滑动窗口的移动：

  1. 窗口扩张：当当前字符不在窗口中时，将字符添加到窗口的哈希表中，并向右移动右指针 r，窗口扩张。
  2. 窗口缩小：如果当前字符已经在窗口中，说明出现了重复，需要移动左指针 l 来缩小窗口，直到当前字符不再出现在窗口中。

3.2 算法步骤

  • 初始化：定义两个指针 l 和 r，分别代表窗口的左右边界，初始时都指向字符串的开始位置。定义一个哈希表 set 来存储窗口内的字符，以及两个变量 res 和 curres 分别用来存储最长不重复子串的长度和当前窗口的长度。

  • 遍历字符串：通过右指针 r 遍历字符串。

    • 检查重复：在每次迭代中，首先检查当前字符 s.charAt(r) 是否已经在哈希表 set 中。如果在，说明出现了重复，需要缩小窗口。
      • 窗口缩小：如果出现重复，通过 while 循环，不断移除左指针 l 指向的字符，并右移 l，直到当前字符不再出现在窗口中。
    • 窗口扩张：将当前字符 s.charAt(r) 添加到哈希表 set 中，并更新当前窗口长度 curres。
    • 更新结果：每次窗口扩张后，比较并更新 res 的值，取 res 和 curres 中的较大值作为新的 res。

  • 返回结果：遍历结束后，返回 res 作为最长不重复子串的长度。

3.3 代码实现

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        /**
        维护一个滑动窗口
        滑动窗口内没有重复的字符
        当当前滑动窗口内，无重复字符时，右指针右移，窗口扩张
        存在重复字符时，左指针右移，窗口缩小

        滑动窗口范围为[l,r]
         */
        int n = s.length();
        int l = 0;
        Set<Character> set = new HashSet<>();
        int res = 0;
        int curres = 0;
        for(int r = 0;r<n;r++){
            while(set.contains(s.charAt(r))){
                set.remove(s.charAt(l));
                l++;
                curres--;
            }
            set.add(s.charAt(r));
            curres ++;
            res = Math.max(res,curres);

        }
        return res;
    }
}

3.4 复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。这是因为每个字符最多被访问两次（一次是窗口扩张，一次是窗口缩小）。
  • 空间复杂度：O(min(n, m))，其中 n 是字符串 s 的长度，m 是字符集的大小。在最坏的情况下，哈希表需要存储所有不同的字符。

4 30.串联所有单词的子串

30. 串联所有单词的子串

困难

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

1
2
3
4
5
6
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

1
2
3
4
5
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

1
2
3
4
5
6
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 和 s 由小写英文字母组成

4.1 题目分析

这个问题要求找出所有包含特定单词集合 words 的子串的起始索引。这里的关键是使用滑动窗口的方法来高效地检查每个可能的子串，同时使用哈希表来跟踪单词的出现频次。

  1. 单词频次映射：首先，我们需要记录 words 数组中每个单词的出现频次，这可以通过一个哈希表（Map）来实现。
  2. 滑动窗口：使用滑动窗口来遍历字符串 s，窗口内包含 words 数组中所有单词的一个或多个实例。
  3. 窗口初始化：对于每种可能的单词划分方式，初始化窗口，并检查第一个窗口是否包含 words 数组中的所有单词。
  4. 窗口滑动：在确认第一个窗口后，继续滑动窗口，每次移动时更新窗口内的单词频次，并检查是否满足条件。
  5. 条件检查：如果窗口内的单词频次与 words 数组中的频次完全匹配，则记录窗口的起始索引。

4.2 算法步骤

  1. 初始化变量：
    • n：words 数组中每个单词的长度。
    • m：words 数组的长度，即单词的数量。
    • ls：字符串 s 的长度。
    • res：用来存储所有满足条件的子串起始索引的列表。
  2. 遍历划分方式：
    • 对于字符串 s 中的每种可能的单词划分方式，检查是否能够形成 words 数组中的单词。
  3. 初始化滑动窗口：
    • 对于每种划分方式，从 s 中取出 m 个单词，并记录它们的出现频次。
  4. 检查 words 数组中的单词：
    • 遍历 words 数组，更新窗口内单词的频次，如果频次减至0，则从哈希表中移除该单词。
  5. **滑动窗口遍历字符串 s**：
    • 继续遍历字符串 s，每次移动窗口时，添加新进入窗口的单词，并移除离开窗口的单词。
    • 如果在任何时候哈希表为空，说明当前窗口包含了 words 数组中的所有单词，记录下当前窗口的起始索引。
  6. 返回结果：
    • 返回所有满足条件的子串起始索引的列表。

4.3 代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        /**
         是438 字母异位词的变体
         逻辑上差不多
         438 题中的步骤如下
         1.初始化pcnt和scnt数组，记录出现的频次
         2.初始化滑动窗口，判断第一个窗口是否满足。
         3.for遍历，判断其他窗口是否满足pcnt和scnt相等。

         本题差不多，只是不再用cnt来记录两个字符串的字母出现频次，而是用Map，此外，本题中也不再是记录单个字母的出现频次，而是记录单词。
         最后，由于是单词，所以还要考虑不同的划分方法

         比如barfoothefoobarman
         有三种划分方式
         bar foo the foo bar man
         b arf oot efo oba rma n
         ba rfo oth efo oba arm an
         遍历这三种划分方式，遍历的时，先初始化最开始的滑动窗口，判断第一个窗口是否满足，之后开始for遍历s数组，判断s的其他窗口是否也满足。
         */
        int n = words[0].length(); // words中字符串的长度，一共有n种划分方式
        int m = words.length; // words 字符串数组的长度，用来遍历字符串，计算Map
        int ls = s.length(); // 字符串s的长度
        List<Integer> res = new ArrayList<>();

        for(int i = 0;i<n;i++){ // n种划分方式
            //2.0 注意这里，只有当i+m*n <=ls 时，i才会有效
            if(i+m*n > ls){
                break;
            }
            // 2.1 初始化滑动窗口
            Map<String,Integer> map = new HashMap<>();
            // 2.1.1 从s中取出m个单词
            for(int j = 0;j<m;j++){
                String word = s.substring(i+j*n,i+(j+1)*n);
                map.put(word,map.getOrDefault(word,0)+1);
            }
            // 2.1.2 遍历words，假如map中存在words中的word，那么map[word]--,最后将map中对应单词出现次数为0的单词全部移除，假如map为空，则说明是一个串联子串

            for(String word:words){
                map.put(word,map.getOrDefault(word,0)-1);
                if(map.get(word)==0){
                    map.remove(word);
                }
            }

            if(map.isEmpty()){
                res.add(i);
            }

            for(int start = i+n;start<=ls-m*n;start+=n){
                String word = s.substring(start+(m-1)*n,start+m*n);
                map.put(word,map.getOrDefault(word,0)+1);
                if(map.get(word)==0){
                    map.remove(word);
                }
                word = s.substring(start-n,start);
                map.put(word,map.getOrDefault(word,0)-1);
                if(map.get(word)==0){
                    map.remove(word);
                }

                if(map.isEmpty()){
                    res.add(start);
                }
            }


        }
        return res;
    }
}

4.4 复杂度分析

  • 时间复杂度：O(m * n * (ls - m * n + 1))，在最坏的情况下，我们需要遍历整个字符串 s 多次，每次遍历都需要检查 m 个单词。
  • 空间复杂度：O(m)，用于存储单词的哈希表。

5 76.最小覆盖子串

76. 最小覆盖子串

困难

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

注意：

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

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

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

提示：

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

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

5.1 题目分析

使用滑动窗口技术，通过动态调整窗口大小来寻找包含字符串 t 所有字符的 s 的最小子串，并利用哈希表高效地进行字符频次比较和更新。

     用两个Map存储
     一个Map ori 存储t中所有字符出现的次数
     一个Map cnt 存储滑动遍历s时滑动窗口内，所有字符出现的次数

     使用一个Check函数比较ori和cnt两个map，比较对于ori中的所有字符，cnt中是不是都出现并并且出现次数>= ori中的
     滑动规则则为：
     check函数满足：当前s的子串能涵盖t的所有字符，记录当前子串，左指针左移
     不满足则右指针右移

5.2 算法步骤

  1. 字符频次统计：首先，使用两个哈希表 ori 和 cnt 分别存储目标字符串 t 中所有字符的出现次数和当前滑动窗口内字符的出现次数。
  2. 滑动窗口初始化：初始化两个指针 l 和 r，分别代表滑动窗口的左右边界。
  3. 窗口扩张：通过移动右指针 r 来扩张窗口，直到窗口内包含了 t 中所有字符的所需数量。
  4. 窗口缩小：当窗口满足条件后（即包含了 t 中所有字符的所需数量），开始移动左指针 l 来缩小窗口，寻找更小的满足条件的子串。
  5. 检查函数：使用一个 check 函数来比较 ori 和 cnt 两个哈希表，检查当前窗口是否包含了 t 中所有字符的所需数量。
  6. 结果更新：每当找到一个满足条件的窗口时，比较并更新记录的最小子串。

5.3 代码实现

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
37
38
39
40
41
42
43
44
class Solution {
    Map<Character,Integer> ori = new HashMap<>();
    Map<Character,Integer> cnt = new HashMap<>();
    public String minWindow(String s, String t) {
        int ls = s.length();
        int lt = t.length();
        if(ls<lt){
            return "";
        }
        //1.构建ori中的值，ori存储t中所有字符出现的次数
        for(int i = 0;i<lt;i++){
            ori.put(t.charAt(i),ori.getOrDefault(t.charAt(i),0)+1);
        }

        //2使用滑动窗口遍历s,[l,r)
        int l = 0;
        int res = Integer.MAX_VALUE;
        String resstr = "";
        for(int r = 0;r<ls;r++){
            cnt.put(s.charAt(r),cnt.getOrDefault(s.charAt(r),0)+1);

            while(check()){
                if(r-l+1<res){
                    resstr = s.substring(l,r+1);
                    res = r-l+1;
                }
                cnt.put(s.charAt(l),cnt.getOrDefault(s.charAt(l),0)-1);
                l++;
            }
        }
        return resstr;
    }

    boolean check(){
        for(Map.Entry<Character,Integer> entry:ori.entrySet()){
            Character key = entry.getKey();
            Integer num = entry.getValue();
            if(cnt.get(key)==null || cnt.get(key)<num){
                return false;
            }
        }
        return true;
    }
}

5.4 复杂度分析

  • 时间复杂度：O(ls + lt)，在最坏的情况下，我们需要遍历整个字符串 s 和 t。
  • 空间复杂度：O(lt)，用于存储字符频次的哈希表。