跳转至

滑动窗口专题

约 4216 个字 708 行代码 4 张图片 预计阅读时间 23 分钟

介绍

所谓滑动窗口，即为同向双指针移动过程中形成的间隔区域，并且这两个指针在移动的过程中不会回退

对于滑动窗口的题目可以抽象为下面的步骤：

  1. 定义窗口两端指针left和right
  2. 进入窗口
  3. 判断
  4. 离开窗口
  5. 循环2、3和4步

滑动窗口类题目一般分为两种：

  1. 定长窗口：代表right和left构成的区间最大长度在整个遍历过程中是固定的，定长窗口更新的特点就是长度大于最大长度就需要更新窗口，并且只需要更新一次就可以重新满足条件，例如下面题目中的力扣438题和力扣30题
  2. 不定长窗口：代表right和left构成的区间长度在整个遍历过程中是不固定的，不定长窗口因为其长度不固定，所以不能通过长度作为条件更新窗口，例如下面题目中的力扣209题、力扣3题、力扣1004题和力扣904题

示例题目

力扣209.长度最小的子数组

问题描述：

Quote

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

示例 2：

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

示例 3：

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

思路分析：

  1. 解法1：暴力解法

    本题首先想到的就是暴力解法，暴力解法的思路很简单，第一层for循环遍历，选出区间左端点，第二层for循环遍历，选出区间右端点，最后一次遍历，将左右区间中的值全部相加求和，标记此时子数组的长度，如此往复直到找到子数组长度最小且子数组中元素之和>=target。根据这个暴力思路得出其时间复杂度为\(O(N^3)\)

    Note

    之后的题目的暴力解法基本类似，所以将不再提示暴力解法，但是实际上的滑动窗口算法就是从暴力解法演变的，因为暴力解法做了一些重复性的比较

  2. 解法2：滑动窗口

    滑动窗口的本质就是双指针算法：一个指针在前面遍历，等到满足一定的条件时再让另一个指针移动，所以现在需要思考的就是如何找到一个指针遍历的条件以及另一个指针遍历的条件。本题主要的目标是找到数组元素之和大于等于target并且满足数组元素最少，所以可以推出求和即为第一个指针遍历的条件，而当第一个指针和第二个指针之间的元素之和大于等于target就是另一个指针遍历的条件，而要求数组元素最少，就是求两个指针的差值最小

Info

「如何找到一个指针遍历的条件」在滑动窗口中也被称为「进窗口」，另一个指针遍历的条件在滑动窗口中也被称为「判断+重新构建窗口」，因为「重新构建窗口」涉及到前面的元素离开原先的窗口，所以也被称为「出窗口」，后续也会以滑动窗口的术语展开

关键步骤：

以数组[2,3,1,2,4,3]为例

单调性：因为题目给出了一个条件正整数的数组，在正整数范围内求和可以得到一个单调性的规律：加的数字越多和越大，所以如果第一次找到了一个和满足>=target，则该下标后的数值即可不需要遍历，例如下图中的4和3即可不需要遍历

正向性：因为在上一次的遍历过程中，已经找到了一组子数组和满足>=target，并且根据单调性可以得出right不需要再向后移动，接下来需要更新left寻找下一组，那么此时right是否需要回退到left的位置重新再来一次遍历呢？答案是不需要（如果回去就退化为了暴力解法），因为left在移动的过程中，区间[left, right]是开始时(left=0)[left, right]区间的子区间，所以此时的区间(left=1)[left, right]中的元素和即为(left=0)[left,right]区间和-left(left=1)=0时的值

一般满足以上两个性质，就可以使用滑动窗口算法，这个算啊可以将暴力解法优化到\(O(N)\)，即只需要一次遍历

在本题中，滑动窗口的两端即为left和right，而滑动窗口中所维护的信息即为子数组之和sum，根据滑动窗口的基本解题步骤可以得出现在需要找到何时进窗口、判断以及何时出窗口

  1. 何时进窗口（移动right扩大当前窗口）：本题中，因为窗口中维护的信息是sum，所以当开始求和时即为进窗口
  2. 判断：本题中窗口更新条件时sum>=target
  3. 何时出窗口（移动left构建新窗口）：本题中，根据判断条件sum>=target可以得出，此条件成立时，证明已经得出了一个合理的结果，需要更新sum和子数组长度len，并让left向后移动（移动窗口，即出窗口），这一过程被称为更新结果

需要注意，本题需要求出子数组长度的最小值，所以保存长度的结果变量len不可以初始化为0，否则最后结果只会为0

Note

更新结果部分一般可能出现在出窗口之前或者出窗口结束之后，具体视题目而定

具体步骤如下：

参考代码：

C++
 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
// 暴力解法
class Solution209_1
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int len = INT_MAX;
        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = 0; j < nums.size(); j++)
            {
                int sum = 0;
                for(int k = i; k <= j; k++)
                {
                    sum += nums[k];
                    if(sum >= target)
                    {
                        len = min(len, j - i + 1);
                    }
                }
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};
C++
 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
class Solution209_2
{
public:
    int minSubArrayLen(int target, std::vector<int> &nums)
    {
        int start = 0;
        int len = INT_MAX; // 定义为最大值可以确保比较时一定可以取到最小值
        int sum = 0;
        for (int end = 0; end < nums.size(); end++)
        {
            // 通过end移动计算起始位置和终止位置区间的和sum
            sum += nums[end];
            // 如果sum大于等于target，说明已经找到符合条件的子数组，可以更新sum和start，准备下一次寻找子数组
            // 此处需要循环判断sum是否在start更新时依旧满足sum>=target，不满足时再更新end继续计算和
            // 否则就相当于移出窗口
            while (sum >= target)
            {
                // 先计算当前满足条件时的下标
                len = std::min(len, end - start + 1);
                // 更新start和sum
                sum -= nums[start];
                start++;
            }
        }

        // 如果不存在指定的子数组，则返回0
        if (len == INT_MAX)
        {
            return 0;
        }

        return len;
    }
};

相关题目

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

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

问题描述：

Quote

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

示例 1:

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

示例 2:

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

示例 3:

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

思路分析：

本题整体思路与例题类似，唯一需要注意的就是因为要找出无重复字符，所以需要涉及到去重操作

参考代码：

C++
 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
// 滑动窗口解法
class Solution3
{
public:
    int lengthOfLongestSubstring(std::string s)
    {
        std::unordered_map<char, int> m;
        int len = 0;
        for (int start = 0, end = 0; end < s.size(); end++)
        {
            // 进入窗口
            // 向哈希表中添加字符，如果字符存在就改变计数器
            m[s[end]]++;

            // 更新窗口——目的是为了移除重复的元素
            while (m[s[end]] > 1)
            {
                m.find(s[start++])->second--;
            }
            len = std::max(len, end - start + 1);
        }

        return len;
    }
};

力扣1004.最大连续1的个数Ⅲ

力扣1004.最大连续1的个数Ⅲ

问题描述：

Quote

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

C++
1
2
3
4
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

C++
1
2
3
4
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

思路分析：

  1. 解法1：暴力解法
  2. 解法2：滑动窗口 本题需要注意使用一个计数器zero统计0的个数而非通过一个变量依次减少直到小于k，从而变向达到翻转0的目的来构建一个滑动窗口，因为小于k不止一个情况，例如k=2时，假设tmpk是记录存储k以便后面重新更新k，tmpk可以有0,1两种情况都小于k，甚至逻辑上还有可能存在负数。但是考虑到大于k只需要考虑一次，尽管大于k有3,4...多种情况，但是第一次大于k只有一种情况，所以通过计数器改变统计当前0的个数

关键步骤：

注意，题目提到最多翻转k个0，所以可能出现翻转0,1,2,3...k，言外之意就是翻转0的个数小于等于k，故存在k特别大而zero计数器一直不可能大于k的情况。综上，考虑在出窗口结束后更新结果

参考代码：

C++
 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
// 滑动窗口算法
class Solution1004
{
public:
    int longestOnes(std::vector<int> &nums, int k)
    {
        int len = 0;
        // int tmpk = k;
        int zeroNum = 0;

        for (int left = 0, right = 0; right < nums.size(); right++)
        {
            // 变量依次减少的方式——复杂且不易控制
            // if(nums[end] == 0)
            // {
            //     tmpk--;
            // }

            // while(tmpk < k)
            // {

            // }

            // 进窗口
            if (nums[right] == 0)
            {
                zeroNum++;
            }

            // 更新窗口
            while (zeroNum > k)
            {
                // 不要在循环内部更新结果
                // len = max(len, right - left + 1);
                if (nums[left++] == 0)
                {
                    zeroNum--;
                }
            }

            len = std::max(len, right - left + 1);
        }

        return len;
    }
};

力扣1658.将x减到0的最小操作数

力扣1658.将x减到0的最小操作数

问题描述：

Quote

给你一个整数数组nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将x恰好减到0，返回最小操作数；否则，返回-1。

示例 1：

C++
1
2
3
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

C++
1
2
输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

C++
1
2
3
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

思路分析：

  1. 解法1：暴力解法
  2. 解法2：滑动窗口 本题使用到正难则反的策略，因为本题既要考虑左侧又要考虑右侧，但是连续的部分是中间区域，所以可以从中间区域下手构建滑动窗口

关键步骤：

本题就可以转换为「求出最长的一段区间（此时剩余区间就是最小的）其中的和大于等于数组和sumNums-x」，需要注意本题有两个特殊情况:

  1. 当sumNums-x == 0时，此时最小的操作数的个数就是整个数组
  2. 当sumNums-x < 0时，说明无法使x减到0，自然也就无法算出sumNums-x == target的情况

参考代码：

C++
 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
class Solution1658_1 
{
public:
    int minOperations(std::vector<int>& nums, int x) 
    {
        int target = std::accumulate(nums.begin(), nums.end(), 0) - x;
        // 特判，当target刚好为0，说明此时最小的操作数的个数就是整个数组
        if(target == 0)
        {
            return nums.size();
        }
        // 定义变量记录区间和
        int sum = 0;
        // 定义变量记录区间长度
        int len = -1;
        for(int start = 0, end = 0; end < nums.size(); end++)
        {
            // 进入窗口
            sum += nums[end];

            // 更新窗口
            while(sum > target && start < end)
            {
                sum -= nums[start++];
            }

            // 可能存在数组中的数据无法使x减到0，自然也就无法算出sumNums-x == target的情况
            if(sum == target)
            {
                len = std::max(len, end - start + 1);
            }
        }

        // 返回最长区间的其他区间总长度即为所求
        return len == -1 ? -1 : nums.size() - len;
    }
};
C++
 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 Solution1658_2 
{
public:
    int minOperations(std::vector<int>& nums, int x) 
    {
        int sum = 0;
        for (int a : nums)
            sum += a;
        int target = sum - x;
        // 细节问题
        if (target < 0)
            return -1;
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) 
        {
            tmp += nums[right];      // 进窗
            while (tmp > target)     // 判断
                tmp -= nums[left++]; // 出窗
            if (tmp == target)       // 更新结果
                ret = std::max(ret, right - left + 1);
        }
        // 此处包括了一种情况：当x与sumNums完全相等的时候，此时区间和永远大于target，因为target为0
        if (ret == -1)
            return ret;
        else
            return nums.size() - ret;
    }
};

力扣904.水果成篮

力扣904.水果成篮

问题描述：

Quote

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

思路分析：

  1. 解法1：暴力解法
  2. 解法2：滑动窗口 根据题目的描述，可以联想出本题涉及到一个窗口的进入和更新：窗口进入：当前元素不存在时，插入到当前容器，窗口更新：当元素个数超过两个时，考虑更新窗口直到重新满足条件，所以可以使用滑动窗口算法

关键步骤：

本题并没有提到每一个元素只出现一次，但是需要确保容器中只有两个元素，所以需要用到可以去重的容器，可以选择的结构：红黑树，容器对应的就是set和map，也可以考虑使用unordered_map或者unordered_set。但是在更新窗口时，如果直接删除容器中的元素可能会因为每一个元素不止出现一次导致提前更新窗口，例如[3,3,3,1,2,1,1,2,3,3,4]，如果直接使用一个红黑树容器，在插入时3,1,2，此时红黑树的元素个数size为3需要更新窗口，进入循环更新逻辑时，因为没有对元素进行计数，导致set直接删除起始指针start指向的第一个3，现在size重新回到2，循环提前结束.所以可以考虑使用map或者unordered_map，如果元素不存在直接插入，否则只更新计数器。最后，更新计数器不可以在更新窗口中更新，因为不能确定一定会出现3种水果

优化思路：

本题因为数据量较小，最大为10万，也可以考虑不使用库中的哈希表，而使用一个数组采用直接定址法，减少时间和空间复杂度

参考代码：

C++
 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
class Solution904_1
{
public:
    int totalFruit(std::vector<int> &fruits)
    {
        int start = 0;
        int len = 0;
        std::unordered_map<int, int> m; // 使用unordered_map，查找的时间复杂度为O(1)
        for (int end = 0; end < fruits.size(); end++)
        {
            // 确定元素是否存在，不存在就添加
            m[fruits[end]]++;
            // 当不满足条件：两个篮子中的水果种类大于2种时调整窗口
            while (m.size() > 2)
            {
                // 直到指定元素的计数器为0时才删除，否则一直减少计数器
                if ((--(m.find(fruits[start])->second)) == 0)
                {
                    m.erase(fruits[start]);
                }
                // 更新窗口
                start++;
            }

            // 更新长度
            len = std::max(len, end - start + 1);
        }

        return len;
    }
};
C++
 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
// 容器优化版
class Solution_2 {
public:
    int totalFruit(std::vector<int>& fruits) {
        int start = 0;
        int len = 0;
        // std::unordered_map<int, int> m; // 使用unordered_map，查找的时间复杂度为O(1)
        int m[100001] = {0}; // 注意初始化，防止随机值导致错误
        // 水果种类
        int kinds = 0;
        for (int end = 0; end < fruits.size(); end++) {
            // 确定元素是否存在，不存在就添加
            if(m[fruits[end]] == 0)
            {
                kinds++;
            }
            m[fruits[end]]++;
            // 当不满足条件：两个篮子中的水果种类大于2种时调整窗口
            while (kinds > 2) {
                // 直到指定元素的计数器为0时才删除，否则一直减少计数器
                if(m[fruits[start]] > 0)
                {
                    m[fruits[start]]--;
                    if (m[fruits[start]] == 0)
                    {
                        kinds--;
                    }
                }

                // 更新窗口
                start++;
            }

            // 更新长度
            len = std::max(len, end - start + 1);
        }

        return len;
    }
};

力扣438.找到字符串中所有字母异位词

力扣438.找到字符串中所有字母异位词

问题描述：

Quote

给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

C++
1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

C++
1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路分析：

  1. 解法1：暴力解法

  2. 解法2：滑动窗口

    分析本题前需要先理解何为「异位词」，所谓「异位」就是不同位置，所以「字母异位词」就代表一个只有字母构成的字符串中的所有字母重新打乱，并且每个字母只能使用一次构成的新字符串。所以本题的题意中，在s中找p的异位词说明s中包含p的异位词，而根据异位词的特点「重新打乱」可以推出构成字母异位词的新字符串中不可以有原字符串不存在的字母，所以可以推出s中涵盖p的每一个异位词长度等于p字符串的长度，利用这个特点就可以使用长度为p字符串长度的定长滑动窗口

关键步骤：

首先要考虑的就是如何判断s中存在p的异位词，最直观的想法就是通过两个哈希表，假设为ori和sub，其中ori哈希表统计s中的字符出现的个数，sub中记录p中的字符出现的个数，在启动窗口前，先统计p中字符出现的个数，题目并没有提到p中的字符不重复，所以通过比较个数是最合理且有效的。在比较过程中，进窗口就是将当前的字符插入到ori哈希表中，如果ori哈希表中和sub哈希表中对应的字符个数相同，说明出现了一个异位词，此时就需要更新一次结果，接下来如果right再继续向后移动导致窗口长度大于固定长度就需要出窗口，本题出窗口的本质就是让left位置的字母的在哈希表中的个数减少1，再更新left

以s = "cbaebabacd", p = "abc"为例，示意图如下：

优化思路：

  1. 容器优化：本题中的s和p都只有字母，所以可以直接使用一个数组哈希表进行字母ASCII值映射
  2. 更新结果比较逻辑优化：本题可以考虑使用一个计数器count统计s中有效字符的个数，更新逻辑分为以下三种：
    1. 当字符进入窗口后，如果当前比较的字符存在与ori中，但不存在于sub中，那么说明不是有效字符，count不变。如果既存在于ori，也存在于sub中，说明是有效字符，改变count。注意更新逻辑为小于等于而不是仅等于，因为可能存在重复字符
    2. 当left所在位置的字符个数更新之前需要更新计数器，分为三种逻辑：
      1. 当出去的字符在哈希表ori中的个数比哈希表sub中的多，此时说明移出去的是多余的字符，不需要更新count
      2. 当出去的字符在哈希表ori中的个数与哈希表sub中的相等，此时说明有效字符被移除，需要更新count
      3. 当出去的字符在哈希表ori中不存在，但是在哈希表sub中存在，此时个数关系就是小于，说明sub中有重复的字符，此时ori中只出现了一次这个重复字符但是要被移除，所以依旧是有效字符被移除，需要更新count，例如s="abacc", p="abbc"
    3. 如果有效字符个数count与p的长度相同，则一定是异位词

参考代码：

C++
 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
// 滑动窗口算法——定长窗口
// 使用库版本
class Solution438_1 {
public:
    std::unordered_map<char, int> ori, sub;
    bool check() {
        for (auto kv : sub) {
            if (ori[kv.first] != kv.second) {
                return false;
            }
        }

        return true;
    }
    std::vector<int> findAnagrams(std::string s, std::string p) {
        std::vector<int> v;
        for(auto ch : p)
        {
            sub[ch]++;
        }
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            // 进入窗口
            ori[s[right]]++;

            // 更新窗口
            if(right - left + 1 > p.size())
            {
                ori[s[left]]--;
                left++;
            }

            // 更新结果
            if(check())
            {
                v.push_back(left);
            }
        }

        return v;
    }
};
C++
 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
// 直接定址法
// 元素有限时，可以考虑使用直接定址法，减少时间和空间的消耗
class Solution438_2 {
public:
    // 元素个数有限时，可以考虑使用直接定址法，减少时间和空间的消耗
    int ori[26] = {0}, sub[26] = {0};
    bool check() {
        for(size_t i = 0; i < 26; i++)
        {
            if(ori[i] != sub[i])
            {
                return false;
            }
        }

        return true;
    }

    std::vector<int> findAnagrams(std::string s, std::string p) {
        std::vector<int> v;
        for(auto ch : p)
        {
            sub[ch - 'a']++;
        }
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            // 进入窗口
            ori[s[right] - 'a']++;

            // 更新窗口
            if(right - left + 1 > p.size())
            {
                ori[s[left] - 'a']--;
                left++;
            }

            // 更新结果
            if(check())
            {
                v.push_back(left);
            }
        }

        return v;
    }
};
C++
 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
// 优化比较逻辑版本
class Solution438_3 {
public:
    // 元素个数有限时，可以考虑使用直接定址法，减少时间和空间的消耗
    int ori[26] = {0}, sub[26] = {0};
    std::vector<int> findAnagrams(std::string s, std::string p) {
        std::vector<int> v;
        // 存储有效字符个数
        int count = 0;
        for(auto ch : p)
        {
            sub[ch - 'a']++;
        }
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            // 进入窗口
            ori[s[right] - 'a']++;
            // 维护有效字符个数
            if(ori[s[right] - 'a'] <= sub[s[right] - 'a'])
            {
                count++;
            }

            // 更新窗口
            if(right - left + 1 > p.size())
            {
                // 出窗口前维护有效字符个数
                if(ori[s[left] - 'a'] <= sub[s[left] - 'a'])
                {
                    count--;
                }

                ori[s[left] - 'a']--;
                left++;
            }

            // 更新结果优化版
            if(count == p.size())
            {
                v.push_back(left);
            }
        }

        return v;
    }
};

力扣30.串联所有单词的子串

力扣30.串联所有单词的子串

问题描述：

Quote

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

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

例如，如果words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。 返回所有串联子串在s中的开始索引。你可以以任意顺序返回答案。

示例 1：

C++
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：

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

示例 3：

C++
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. 解法1：暴力解法
  2. 解法2：滑动窗口 本题主体思路与上题相同，但是需要注意的是，本题比较的不是字符，而是字符串，题目提到「words中所有字符串长度相同」，就可以考虑使用定长滑动窗口，另外可以考虑使用整体法，因为题目提到了words中的每一个字符的长度相同，并且words数组的长度并不是很长，比较时取出s中长度与words中每一个字符串长度相同的子字符串比较，剩余的思路就和上题一样

关键步骤：

需要注意，本题并不能保证符合要求的串联子串的第一个字符在s中的位置一定是words每个字符串长度的整数倍，所以需要进行words数组每一个字符串的长度次的滑动窗口，示意图如下：

参考代码：

C++
 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
// 滑动窗口算法——定长
class Solution30 {
public:
    std::unordered_map<std::string, int> ori, sub;
    std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
        std::vector<int> v;
        for(auto& str : words)
        {
            sub[str]++;
        }
        // 每个单词的长度
        int sz = words[0].size();
        // 控制滑动窗口执行的次数
        for(int count = 0; count < sz; count++)
        {
            // 滑动窗口
            // right+sz总共就是words的总长度，所以需要注意可以相等
            for(int left = count, right = count, cnt = 0; right + sz <= s.size(); right += sz)
            {
                // 进入窗口
                std::string str = s.substr(right, sz);
                ori[str]++;
                // 判断是否更新有效字符个数
                // 先判断sub中有对应的字符串，再进行比较，否则当sub中没有指定的元素会进行插入，从而产生时间和空间消耗
                if(sub.count(str) && ori[str] <= sub[str])
                {
                    cnt++;
                }

                // 更新窗口
                if(right - left + 1 > sz * words.size())
                {
                    std::string tmp = s.substr(left, sz);
                    // 更新计数器
                    if(sub.count(tmp) &&ori[tmp] <= sub[tmp])
                    {
                        cnt--;
                    }

                    ori[tmp]--;
                    left += sz;
                }

                // 更新结果
                if(cnt == words.size())
                {
                    v.push_back(left);
                }
            }
            ori.clear();
        }
        return v;
    }
};

力扣76.最小覆盖子串

力扣76.最小覆盖子串

问题描述：

Quote

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

注意：

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

示例 1：

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

示例 2：

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

示例 3:

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

思路分析：

  1. 解法1：暴力解法 枚举出所有包含查找子串的所有字符的字符串，比较长度取出最小的子串
  2. 解法2：滑动窗口 根据暴力解法，每一次枚举所有包含的子串这个过程中涉及到一些重复的步骤，例如已经完全包含内容的子串被多次枚举，而如果需要将这个过程中的枚举次数减少，策略就是找到最接近最优解的一个子串，整个遍历过程中，当一个指针在遍历s字符串时，这个指针离起始位置的距离越来越远，此时与起始位置的指针就构成一个区间，而当刚好满足找到子串的条件时，就需要减小区间，确保能找到更小一点的区间，而这个过程就正好满足不定长滑动窗口的过程

关键步骤：

题目提到了t字符串中的重复字符也需要完全匹配，所以需要使用哈希表来统计出现的次数

构建窗口：在t字符串的哈希表sub中找s字符串中的字符，如果出现添加到另一个哈希表ori中进行计数，方便更新窗口时比较；

更新窗口：当哈希表sub中字符的个数与ori中对应的字符个数相同或者ori中的对应字符个数大于sub中字符的个数，说明一定存在子串包含t中的所有字符，此时就需要更新窗口。否则一定不需要更新窗口。更新窗口的过程中需要记录当前子串的长度已经起始位置方便最后截取字符串，注意一定要比较新的len和已经记录的len，当新的len较小时再更新起始位置，否则会出现起始位置一直被更新，包括新len和旧len相同的情况

更新逻辑：让ori中的字符个数与sub中的字符个数不匹配，即类似于从ori中依次移除出现于t中的字符

本题只需要考虑短的字符串中的字符即可，对于s字符串来说，其他字符是否存在不需要考虑（因为插入会有一定时间和空间消耗）

优化思路：

  1. 容器优化：本题因为只含有字母，所以可以考虑使用一个数组形式的哈希表。注意因为在函数中要比较种类，所以在映射开始之前需要先判断某个字符是不是第一次出现，如果是第一次出现种类计数器就更新，否则就不更新
  2. 更新结果逻辑优化：与前面类似，本次优化版本主要优化更新结果逻辑，利用一个变量来统计字符种类，此处不是字符个数。统计字符种类的逻辑与字符个数不同，统计种类时只需要保证出现的字符是t中的字符且对应字符出现的个数等于t中对应字符的个数就算一次种类更新，否则就不算。之所以要确保个数相等是因为t中可能存在重复字符，出现重复字符必须保证s中也有相同数量的重复字符，如果只统计第一次出现，则不能保证s中的重复字符数量与t中相同，而如果是统计字符个数只需要满足是t中的字符就更新

参考代码：

C++
 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
// 滑动窗口
class Solution76_1 {
public:
    std::unordered_map<char, int> ori, sub;
    // 判断字符个数
    bool check()
    {
        for(auto& kv : sub)
        {
            // 当ori中对应的字符个数少于sub中对应字符的个数时说明此时并不满足覆盖条件
            if(ori[kv.first] < kv.second)
            {
                return false;
            }
        }

        return true;
    }
    std::string minWindow(std::string s, std::string t) {
        int len = INT_MAX;
        int start = 0;
        // 统计t中字符出现的次数
        for(auto& ch : t)
        {
            sub[ch]++;
        }

        for(int left = 0, right = 0; right < s.size(); right++)
        {
            // 进窗口
            // ori[s[right]]++;
            // 只有含有t中字符的时候才插入
            if(sub.find(s[right]) != sub.end())
            {
                ori[s[right]]++;
            }
            // 更新窗口
            while(check())
            {
                // 更新结果
                // start = left;
                // len = min(len, right - left + 1);
                if(right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                // ori[s[left]]--;
                // 只有是t中的字符才删除
                if(sub.find(s[left]) != sub.end())
                {
                    ori[s[left]]--;
                }
                left++;
            }
        }

        return len == INT_MAX ? std::string() : s.substr(start, len);
    }
};
C++
 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
class Solution76_2 {
public:
    std::unordered_map<char, int> ori, sub;
    std::string minWindow(std::string s, std::string t) {
        int len = INT_MAX;
        int start = 0;
        // 统计t中字符出现的次数
        for(auto& ch : t)
        {
            sub[ch]++;
        }

        // 使用count统计字符种类
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            // 进窗口
            // ori[s[right]]++;
            // 只有含有t中字符的时候才插入
            if(sub.find(s[right]) != sub.end())
            {
                ori[s[right]]++;
                // 统计字符种类
                if(ori[s[right]] == sub[s[right]])
                {
                    count++;
                }
            }
            // 更新窗口
            while(count == sub.size())
            {
                // 更新结果
                // start = left;
                // len = min(len, right - left + 1);
                if(right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                // ori[s[left]]--;
                // 只有是t中的字符才删除
                if(sub.find(s[left]) != sub.end())
                {
                    // 更新计数器
                    if(ori[s[left]] == sub[s[left]])
                    {
                        count--;
                    }
                    ori[s[left]]--;
                }
                left++;
            }
        }

        return len == INT_MAX ? std::string() : s.substr(start, len);
    }
};
C++
 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
class Solution76_3 {
public:
    // unordered_map<char, int> ori, sub;
    int ori[128] = {0}, sub[128] = {0};
    // 判断字符个数
    std::string minWindow(std::string s, std::string t) {
        int len = INT_MAX;
        int start = 0;
        // 统计t中字符出现的次数
        // 种类计数器
        int kinds = 0;
        for(auto& ch : t)
        {
            // 第一次出现的字符，更新种类计数器
            if(sub[ch] == 0)
            {
                kinds++;
            }
            sub[ch]++;
        }

        // 使用count统计字符种类
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            ori[s[right]]++;
            // 统计字符种类
            if(ori[s[right]] == sub[s[right]])
            {
                count++;
            }
            // 更新窗口
            while(count == kinds)
            {
                // 更新结果
                if(right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                // 更新计数器
                if(ori[s[left]] == sub[s[left]])
                {
                    count--;
                }
                ori[s[left]]--;
                left++;
            }
        }

        return len == INT_MAX ? std::string() : s.substr(start, len);
    }
};