AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

算法和数据结构解析-5 : 滑动窗口问题

作者：AllinToyou | 2024-03-20 23:57:50

踩

滑动窗口

1. 简介

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作，它的原理与网络传输TCP协议中的滑动窗口协议（Sliding Window Protocol）基本一致。

这种技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。滑动窗口主要应用在数组和字符串上。

例如，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，可以得到一组结果 res。

因为滑动窗口是靠窗口起始、结束两个位置来表示的，所以滑动窗口也可以看作特殊的“双指针”。

2. 滑动窗口最大值（来自leetcode.com）

2.1 题目说明

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例1:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置最大值

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,-1], k = 1

输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2

输出：[11]

示例 5：

输入：nums = [4,-2], k = 2

输出：[4]

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

2.2 分析

这是一个典型的滑动窗口的问题。由于滑动窗口的大小k被限定在[1, nums.length]，所以我们可以直接推出窗口的个数为nums.length - k + 1。

2.3 方法一：暴力法

最简单直接的方法，就是遍历每个滑动窗口，找到每个窗口的最大值


    // 方法一：暴力法，遍历每一个窗口，对每个窗口遍历每个元素求最大值
    public int[] maxSlidingWindow(int[] nums, int k){
        // 定义一个结果数组，总共有n-k+1个窗口
        int[] result = new int[nums.length -k + 1];
 
        // 遍历数组，从0到n-k,作为滑动窗口的起始位置
        for ( int i = 0; i < nums.length - k; i++){
            // 找窗口内的最大值，定义一个变量来保存
            int max = nums[i];
            // 遍历窗口中的每一个元素，比较大小
            for (int j = i; j < i+k; j ++){
                if ( nums[j] > max ){
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        return result;
    }

复杂度分析

时间复杂度： O(Nk)，双重循环，外层遍历数组循环N次，内层遍历窗口循环k次，所以整体就是O(N) * O(k) = O(Nk)，表现较差。在leetcode上提交，会发现超出了题目要求的运行时间限制。

空间复杂度：O(N-k)，输出数组用到了N-k+1的空间。

2.4 方法二：大顶堆

如何优化时间复杂度呢？可以使用堆。

构建一个大顶堆（Max Heap），那么堆顶元素 heap[0] 永远是最大的。每次移动窗口的时候，我们只要维护这个堆、在里面插入删除元素，然后返回堆顶元素heap[0]就可以了。

在代码中，我们可以用一个优先队列（Priority Queue）来实现大顶堆。


    // 方法二：使用大顶堆
    public int[] maxSlidingWindow2(int[] nums, int k){
        // 定义一个结果数组，总共有n-k+1个窗口
        int[] result = new int[nums.length -k + 1];
 
        // 用优先队列实现一个大顶堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
 
        // 准备工作：构建大顶堆，将第一个窗口元素（前k个）放入堆中
        for ( int i = 0 ; i < k; i ++){
            priorityQueue.add(nums[i]);
        }
        // 当前大顶堆的堆顶元素就是第一个窗口的最大值
        result[0] = priorityQueue.peek();
 
        // 遍历所有窗口
        for ( int j = 1 ; j < nums.length - k ; j ++){
            priorityQueue.remove(nums[j-1]);        // 删除堆中上一个窗口的元素
            priorityQueue.add(nums[j+k-1]);         // 添加当前窗口的最后一个元素进堆
            result[j] = priorityQueue.peek();
        }
        return result;
    }

复杂度分析

时间复杂度： O(Nlog(k))，在大小为 k 的堆中插入一个元素只需要消耗 log(k) 时间，因此这样改进后，算法的时间复杂度为O(Nlog(k))。但提交依然会超出时间限制。

空间复杂度：O(N)，输出数组用到了O(N-k+1)的空间，大顶堆用了O(k)。

2.5 方法三：双向队列

使用堆看起来不错，但离题目要求还有差距。能否得到O(N) 的算法呢？

我们发现，窗口在滑动过程中，其实数据发生的变化很小：只有第一个元素被删除、后面又新增一个元素，中间的大量元素是不变的。也就是说，前后两个窗口中，有大量数据是重叠的。

[1, 3, -1,] -3, 5, 3, 6, 7

1, [3, -1, -3,] 5, 3, 6, 7

1, 3, [-1, -3, 5,] 3, 6, 7

自然想到，其实可以使用一个队列来保存窗口数据：窗口每次滑动，我们就让后面的一个元素（-3）进队，并且让第一个元素（1）出队。进出队列的操作，只要耗费常数时间。

这种场景，可以使用 双向队列（也叫双端队列Dequeue），该数据结构可以从两端以常数时间压入/弹出元素。

在构建双向队列的时候，可以采用删除队尾更小元素的策略，所以，得到的其实就是一个 从大到小排序 的队列。

这样存储的元素，可以认为是遵循“更新更大”原则的。

具体代码如下：


    // 方法三： 使用双向队列
    public int[] maxSlidingWindow3(int[] nums, int k){
        // 定义一个结果数组，总共有n-k+1个窗口
        int[] result = new int[nums.length -k + 1];
 
        // 定义双向队列，保存元素的索引
        ArrayDeque<Integer> deque = new ArrayDeque<>();
 
        // 初始化双向队列，处理第一个窗口的数据
        for (int i = 0; i < k ; i++){
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
 
        result[0] = nums[deque.getFirst()];
 
        // 遍历窗口
        for (int i = k; i < nums.length; i++){
            // 判断如果上一个窗口删掉的就是窗口最大值，那么需要将队列中的最大值删掉
            if (!deque.isEmpty() && deque.getFirst() == i-k){
                deque.removeFirst();
            }
            // 判断新增元素是否可以删除队尾元素
            // 如果队尾元素小于当前元素，直接删除
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
                deque.removeLast();
            }
            deque.addLast(i);
 
            // 保存结果
            result[i - k + 1] = nums[deque.getFirst()];
        }
        return result;
    }

复杂度分析

时间复杂度：O(N)，每个元素被处理两次：其索引被添加到双向队列中，以及被双向队列删除。

空间复杂度： O(N)，输出数组使用了 O(N−k+1) 空间，双向队列使用了O(k)。

片段解析：


for (int i = 0; i < k; i++) {
    while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
        deque.removeLast();
    }
    deque.addLast(nums[i]);
}

在这段代码中，我们使用一个循环来遍历窗口的前 k 个元素。在每次循环中，我们进行以下操作：

首先，我们检查双向队列 deque 是否为空，并且当前元素 nums[i] 是否大于队尾元素所对应的 nums 值。
如果条件满足，说明队尾元素不可能成为当前窗口的最大值，因此我们将队尾元素从队列中移除，以确保队列中的元素保持递减的顺序。
接下来，我们将当前元素 nums[i] 添加到队尾，因为它有可能成为当前窗口的最大值。

通过这样的处理，我们在初始化阶段就可以获得窗口的初始最大值，并且保证双向队列中的元素始终保持递减的顺序。最后，队首元素即为初始窗口的最大值。

2.6 方法四：左右扫描

上面的算法，时间复杂度已经可以满足要求了，空间复杂度也不高；但是用到了双向队列这样的高级数据结构，具体算法也有些繁琐。

这里再介绍另一种巧妙的算法：

算法的主要思想，是将输入数组分割成有 k 个元素的块，然后分别从左右两个方向进行扫描统计块内的最大值，最后进行合并。这里有一些借鉴了分治和动态规划的思想。

分块的时候，如果 n % k != 0，则最后一块的元素个数可能更少。

开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。

情况 1 比较简单。建立数组 left，其中 left[j] 是从块的开始到下标 j 最大的元素，方向左->右。

为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向右->左。right 数组和 left 除了方向不同以外基本一致。

两数组合在一起，就可以提供相邻两个块内元素的全部信息。

现在我们考虑从下标 i 到下标 j的滑动窗口。可以发现，这个窗口其实可以堪称两部分：以两块的边界（比如叫做m）为界，从i到m属于第一个块，这部分的最大值，应该从右往左，看right[i]；而从m到j属于第二个块，这部分的最大值应该从左往右，看left[j]。因此合并起来，整个滑动窗口中的最大元素为 max(right[i], left[j])。

同样，如果是第一种情形，都在一个块内，用上面的公式也是正确的（这时right[i] = left[j]，都是块内最大值）。

这个算法时间复杂度同样是O(N)，优点是不需要使用除数组之外的任何数据结构。

代码如下：


    // 方法四： 使用左右扫描
    public int[] maxSlidingWindow4(int[] nums, int k){
        int n = nums.length;
        //定义一个结果数组
        int[] result = new int[nums.length -k + 1];
 
        // 定义存放快内最大值得left和right数组
        int[] right = new int[n];
        int[] left = new int[n];
 
        for (int i = 0; i < n; i++) {
            //1.从左到右
            if ( i % k == 0 ) {
                // 如果能整除，那就是块的起始位置
                left[i] = nums[i];
            }else{
                // 如果不是起始位置，就直接跟left[i-1]取最大值即可
                left[i] = Math.max(left[i-1],nums[i]);
            }
 
            // 2.从右到左
            int j = n - 1 - i;  // j就是倒数的i
            // k-1，比如k=3，n=5，此时从右往左，为 5%3=5-3,4%3=4-3,
            if ( j % k == k - 1  || j == n - 1){
                right[j] = nums[j];
            }else{
                right[j] = Math.max(right[j+1],nums[j]);
            }
        }
 
        // 对每个窗口计算最大值
        for (int i = 0 ; i < n - k + 1; i++){
            result[i] = Math.max(right[i], left[i+k-1]);
        }
 
        return result;
    }

复杂度分析

时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次（实际代码中只有两个循环，左右扫描是对称的，我们在一次遍历中同时处理了）。因为避免了出队入队的操作，所以这个算法在实际运行中，耗费时间要明显少于之前的算法。

空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组。

3. 最小覆盖子串

3.1 题目说明

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

示例 2：

输入：s = "a", t = "a"

输出："a"

提示：

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

3.2 分析

所谓“子串”，指的是字符串中连续的一部分字符集合。这就要求我们考察的所有字符，应该在同一个“窗口”内，这样的问题非常适合用滑动窗口的思路来解决。

而所谓的“最小子串”，当然就是符合要求的、长度最小的子串了。

另外还有一个小细节：需要找出“包含T所有字符的最小子串”，那T中的字符会不会有重复呢？给出的示例“ABC”没有重复，但提交代码之后会发现，测试用例是包含有重复字符的T的，比如“ABBC”在这种情况下，重复出现的字符“B”在子串中也要重复出现才可以。

3.3 方法一：暴力法

最简单直接的方法，就是直接枚举出当前字符串所有的子串，然后一一进行比对，选出覆盖T中所有字符的最小的那个。进一步我们发现，其实只需要枚举长度大于等于T的子串就可以了。

这里的核心问题是，怎样判断一个子串中包含了T中的所有字符？

如果T中没有重复，那这个非常简单，只要再遍历一遍T，依次检查每个字符是否包含就可以了；但现在T中字符可能重复，如果一个字符“A”重复出现3次，那我们寻找的子串中也必须有3个“A”。

所以我们发现，只要统计出T每个字符出现的次数，然后在子串中进行比对就可以。这可以用一个HashMap来进行存储，当然也可以更简单的只用一个数组来存。

子串S符合要求的条件是：统计T中每个字符出现的次数，全部小于等于在S中出现次数。

代码如下：


    // 方法一：暴力法，枚举s中所有子串
    public String minWindow(String s, String t) {
        // 定义最小子串，保存结果，初始为空字符串
        String minSubString = "";
        // 定义一个HashMap，保存t子串字符出现的次数
        HashMap<Character,Integer> tCharFrequency = new HashMap<>();
 
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = tCharFrequency.getOrDefault(c,0);
            tCharFrequency.put(c,count+1);
        }
 
        // 接下来在s中搜索覆盖子串
        // 遍历所有字符，作为当前子串的起始位置
        for (int j = 0; j < s.length(); j++){
            // 遍历j之后不小于t长度的位置，作为子串的结束位置
            for ( int k = j + t.length(); k < s.length() ; k++){
                // 统计s子串中每个字符出现的频次
                // 定义一个HashMap,保存s子串中字符出现的频次
                HashMap<Character,Integer> subStrCharFrequency  = new HashMap<>();
                // 统计子串中字符频次
                for (int h = j; h < k; h++){
                    char c = s.charAt(h);
                    int count = subStrCharFrequency .getOrDefault(c,0);
                    subStrCharFrequency .put(c,count+1);
                }
                // 如果当前子串符合覆盖子串的要求，并且比之前的最小子串要短，就替换
                if (check(tCharFrequency,subStrCharFrequency) && ( k - j < minSubString.length() || minSubString.equals(""))){
                    minSubString = s.substring(j,k);
                }
            }
        }
        return minSubString;
    }
    // 定义一个方法，用来检查子串是否是一个覆盖t的子串
    private boolean check(HashMap<Character, Integer> tChar, HashMap<Character, Integer> jChar) {
        // 遍历t中每个字符的频次，与subStr进行比较
        for (char c: tChar.keySet()){
            if ( jChar.getOrDefault(c,0) < tChar.get(c)){
                return false;
            }
        }
        return true;
    }

复杂度分析

时间复杂度：O(|s|^3)，事实上，应该写作O(|s|^3+|t|)，这里|s|表示字符串s的长度，|t|表示t的长度。我们枚举s所有的子串，之后又要对每一个子串统计字符频次，所以是三重循环，耗费O(|s|^3)。另外还需要遍历t统计字符频次，耗费O(|t|)。t的长度本身要小于s，而且本题的应用场景一般情况是关键字的全文搜索，t相当于关键字，长度应该远小于s，所以可以忽略不计。

空间复杂度：O(C)，这里C表示字符集的大小。我们用到了HashMap来存储S和T的字符频次，而每张哈希表中存储的键值对不会超过字符集的大小。

3.4 方法二：滑动窗口

暴力法的缺点是显而易见的：时间复杂度过大，超出了运行时间限制。在哪些方面可以优化呢？

仔细观察可以发现，我们在暴力求解的时候，做了很多无用的比对：对于字符串“ADOBECODEBANC”，当找到一个符合条件的子串“ADOBEC”后，我们会继续仍以“A”作为起点扩展这个子串，得到一个符合条件的“ADOBECO”——它肯定符合条件，也肯定比之前的子串长，这其实是完全不必要的。

代码实现上，我们可以定义两个指针：指向子串“起始点”的左指针，和指向子串“结束点”的右指针。它们一个固定、另一个移动，彼此交替向右移动，就好像开了一个大小可变的窗口、在不停向右滑动一样，所以这就是非常经典的滑动窗口解决问题的应用场景。所以有时候，滑动窗口也可以归类到双指针法。


    // 方法二：滑动窗口
    public String minWindow2(String s, String t) {
        // 定义最小子串，保存结果，初始为空字符串
        String minSubString = "";
        // 定义一个HashMap，保存t子串字符出现的次数
        HashMap<Character,Integer> tCharFrequency = new HashMap<>();
 
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = tCharFrequency.getOrDefault(c,0);
            tCharFrequency.put(c,count+1);
        }
 
        int start = 0,end = t.length();
        while ( end <= s.length()){
            // 统计s子串中每个字符出现的频次
            // 定义一个HashMap,保存s子串中字符出现的频次
            HashMap<Character,Integer> subStrCharFrequency  = new HashMap<>();
            // 统计子串中字符频次
            for (int k = start; k < end; k++){
                char c = s.charAt(k);
                int count = subStrCharFrequency .getOrDefault(c,0);
                subStrCharFrequency .put(c,count+1);
            }
            // 如果当前子串符合覆盖子串的要求，并且比之前的最小子串要短，就替换
            if (check(tCharFrequency,subStrCharFrequency)){
                if( minSubString.equals("") || end - start < minSubString.length()){
                    minSubString = s.substring(start,end);
                }
                // 只要是覆盖子串，就移动初始位置，缩小窗口，寻找当前的局部最优解
                start ++;
            }else {
                // 如果不是覆盖子串，需要扩大窗口，继续寻找新的子串
                end ++;
            }
        }
        return minSubString;
    }

复杂度分析

时间复杂度：O(|s|^2)，尽管运用双指针遍历字符串，可以做到线性时间O(|s|)，但内部仍需要循环遍历子串，总共消耗O(|s|)*O(|s|)=O(|s|^2)。

空间复杂度：O(C)，这里C表示字符集的大小。同样用到了HashMap来存储S和T的字符频次，而每张哈希表中存储的键值对不会超过字符集的大小。

3.5 方法三：滑动窗口优化

这里考虑进一步优化：

我们计算子串S的字符频次时，每次都要遍历当前子串，这做了很多重复工作。

其实，每次都只是左指针或右指针做了一次右移，只涉及到一个字符的增减。我们不需要重新遍历子串，只要找到移动指针之前的S中，这个字符的频次，然后再加一或者减一就可以了。

具体应该分左指针右移和右指针右移两种情况讨论。

左指针i右移（i –> i+1）。这时子串长度减小，减少的一个字符就是s[i]，对应频次应该减一。
右指针j右移（j -> j+1）。这时子串长度增加，增加的一个字符就是s[j]，对应频次加1。

代码如下：


    // 方法三：滑动窗口优化
    public String minWindow3(String s, String t) {
        // 定义最小子串，保存结果，初始为空字符串
        String minSubString = "";
        // 定义一个HashMap，保存t子串字符出现的次数
        HashMap<Character,Integer> tCharFrequency = new HashMap<>();
 
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = tCharFrequency.getOrDefault(c,0);
            tCharFrequency.put(c,count+1);
        }
        // 统计s子串中每个字符出现的频次
        HashMap<Character,Integer> subStrCharFrequency  = new HashMap<>();
 
        // 定义左右指针，指向滑动窗口的起始和结束位置
        int start = 0,end = 1;
        // 外层while循环主要移动end指针
        while ( end <= s.length()){
 
            // end增加之后，新增的字符
            char newChar = s.charAt(end - 1);
 
            // 新增字符频次加1
            if(tCharFrequency.containsKey(newChar)){
                subStrCharFrequency.put(newChar,subStrCharFrequency.getOrDefault(newChar,0)+1);
            }
 
            // 如果当前子串符合覆盖子串的要求，并且比之前的最小子串要短，就替换
            // 内层while移动start指针
            while (check(tCharFrequency,subStrCharFrequency) && start < end){
                if( minSubString.equals("") || end - start < minSubString.length()){
                    minSubString = s.substring(start,end);
                }
 
                // 对要删除的字符，频次减1
                char removedChar = s.charAt(start);
 
                if(tCharFrequency.containsKey(removedChar)){
                    subStrCharFrequency.put(removedChar,subStrCharFrequency.getOrDefault(removedChar,0)-1);
                }
 
                // 只要是覆盖子串，就移动初始位置，缩小窗口，寻找当前的局部最优解
                start ++;
            }
            // 如果不是覆盖子串，需要扩大窗口，继续寻找新的子串
             end ++;
        }
        return minSubString;
    }

复杂度分析

时间复杂度：O(|s|)。尽管有双重循环，但我们可以发现，内外两重循环其实做的只是分别移动左右指针。最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。另外，每次调用check方法检查是否可行，会遍历整个 t 的哈希表。

哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为 O(C⋅∣s∣+∣t∣)。如果认为t的长度远小于s，可以近似为O(|s|)。

这种解法实现了线性时间运行。

空间复杂度：O(C)，这里C表示字符集的大小。同样用到了HashMap来存储S和T的字符频次，而每张哈希表中存储的键值对不会超过字符集的大小。

3.6 方法四：滑动窗口进一步优化

我们判断S是否满足包含T中所有字符的时候，调用的方法check其实又是一个暴力法：遍历T中所有字符频次，一一比对。上面的复杂度分析也可以看出，遍历s只用了线性时间，但每次都要遍历一遍T的频次哈希表，这就耗费了大量时间。

我们已经知道，每次指针的移动，只涉及到一个字符的增减。所以我们其实不需要知道完整的频次HashMap，只要获取改变的这个字符的频次，然后再和T中的频次比较，就可以知道新子串是否符合要求了。


    // 方法四：滑动窗口进一步优化
    public String minWindow4(String s, String t) {
        // 定义最小子串，保存结果，初始为空字符串
        String minSubString = "";
        // 定义一个HashMap，保存t子串字符出现的次数
        HashMap<Character,Integer> tCharFrequency = new HashMap<>();
 
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = tCharFrequency.getOrDefault(c,0);
            tCharFrequency.put(c,count+1);
        }
        // 统计s子串中每个字符出现的频次
        HashMap<Character,Integer> subStrCharFrequency  = new HashMap<>();
 
        // 定义左右指针，指向滑动窗口的起始和结束位置
        int start = 0,end = 1;
 
        int charCount = 0;
 
        // 外层while循环主要移动end指针
        while ( end <= s.length()){
 
            // end增加之后，新增的字符
            char newChar = s.charAt(end - 1);
 
            // 新增字符频次加1
            if(tCharFrequency.containsKey(newChar)){
                subStrCharFrequency.put(newChar,subStrCharFrequency.getOrDefault(newChar,0)+1);
                // 如果子串中频次小于t中频次，当前字符就有贡献
                if( subStrCharFrequency.get(newChar) <= tCharFrequency.get(newChar) )
                    charCount ++;
            }
 
            // 如果当前子串符合覆盖子串的要求，并且比之前的最小子串要短，就替换
            // 内层while移动start指针
            while (charCount == t.length() && start < end){
                if( minSubString.equals("") || end - start < minSubString.length()){
                    minSubString = s.substring(start,end);
                }
 
                // 对要删除的字符，频次减1
                char removedChar = s.charAt(start);
 
                if(tCharFrequency.containsKey(removedChar)){
                    subStrCharFrequency.put(removedChar,subStrCharFrequency.getOrDefault(removedChar,0)-1);
                    // 如果子串中的频次如果不够t中的频次，贡献值减少
                    if ( subStrCharFrequency.get(removedChar) < tCharFrequency.get(removedChar) )
                        charCount--;
                }
 
                // 只要是覆盖子串，就移动初始位置，缩小窗口，寻找当前的局部最优解
                start ++;
            }
            // 如果不是覆盖子串，需要扩大窗口，继续寻找新的子串
            end ++;
        }
        return minSubString;
    }

时间复杂度：O(|s|)。同样，内外双重循环只是移动左右指针遍历了两遍s；而且由于引入了charCount，对子串是否符合条件的判断可以在常数时间内完成，所以整体时间复杂度为O(|s|+|t|)，近似为O(|s|)。

空间复杂度：O(C)，这里C表示字符集的大小。同样用到了HashMap来存储S和T的字符频次，而每张哈希表中存储的键值对不会超过字符集的大小。

4. 找到字符串中所有字母异位词

“字母异位词”，指“字母相同，但排列不同的字符串”。注意这里所说的“排列不同”，是所有字母异位词彼此之间而言的，并不是说要和目标字符串p不同。

另外，我们同样应该考虑，p中可能有重复字母。

示例 1:

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

4.1 方法一：暴力法

最简单的想法，自然还是暴力法。就是直接遍历s中每一个字符，把它当作子串的起始，判断长度为p.length()的子串是否是p的字母异位词就可以了。

考虑到子串和p中都可能有重复字母，我们还是用一个额外的数据结构pCharCounts[]，来记录P每个字母的出现频次。由于本题的字符串限定只包含小写字母，所以我们可以简单地用一个长度为26的int类型数组来表示，每个位置存放的分别是字母a~z的出现个数。


    /**
     * 方法一：暴力法
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p){
        int[] pCharCounts = new int[26];
        for ( int i = 0; i < p.length(); i++){
            // p.charAt(i) 获取int[]的index，++表示该下标的值+1，即对该下表的字符+1频次
            pCharCounts[p.charAt(i) - 'a']++;
        }
 
        ArrayList<Integer> result = new ArrayList<>();
        // 遍历s,外层循环
        for (int i = 0; i <= s.length() - p.length(); i++){
            // 表示是异位体
            boolean isMatch = true;
            // 移动区域的字母
            int[] subStrCharCounts = new int[26];
 
            // 内层循环开始遍历
            for (int j = i; j < i + p.length(); j++){
                // 对s字符串的每个字符计算频次
                subStrCharCounts[s.charAt(j) - 'a']++;
                // 如果s字符串当前字符频次大于p字符串的当前字符频次，说明p字符串的当前字符为空或者s字符串的当前字符数量超了，同等length里不满足异位体
                // 不满足异位体条件，isMatch为false，跳过当前循环
                if (subStrCharCounts[s.charAt(j) - 'a'] > pCharCounts[s.charAt(j) - 'a']){
                    isMatch = false;
                    break;
                }
            }
            // 满足异位体条件，添加当前起始下标
            if (isMatch){
                result.add(i);
            }
        }
        return result;
    }

复杂度分析

时间复杂度：O(|s| * |p|)，其中|s|表示s的长度，|p|表示p的长度。时间开销主要来自双层循环，循环的迭代次数分别是(s.length-p.length+1)和 p.length, 所以时间复杂度为O((|s|-|p|+1) * |p|), 去除低阶复杂度，最终的算法复杂度为 O(|s| * |p|)。

空间复杂度：O(1)。需要两个大小为 26 的计数数组，分别保存p和当前子串的字母个数。尽管循环迭代过程中在不断申请新的空间，但是上一次申请的数组空间应该可以得到复用，所以实际上一共花费了2个数组的空间，因为数组大小是常数，所以空间复杂度为O(1)。

4.2 方法二：滑动窗口（双指针 1）

暴力法的缺点是显而易见的：时间复杂度较大，运行耗时较长。

我们在暴力求解的时候，其实对于很多字母是做了多次统计的。子串可以看作字符串上开窗截取的结果，自然想到，可以定义左右指针向右移动，实现滑动窗口的作用。在指针移动的过程中，字符只会被遍历一次，时间复杂度就可以大大降低。


    /**
     * 方法二：滑动窗口
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams2(String s, String p){
        int[] pCharCounts = new int[26];
        for ( int i = 0; i < p.length(); i++){
            // p.charAt(i) 获取int[]的index，++表示该下标的值+1，即对该下表的字符+1频次
            pCharCounts[p.charAt(i) - 'a']++;
        }
 
        ArrayList<Integer> result = new ArrayList<>();
 
        // 统计子串中所有字符频次
        int[] subStrCharCounts = new int[26];
 
        int start = 0,end = 1;
 
        // 移动指针，总是截取字符出现频次全部小于p中字符频次的子串
        while ( end <= s.length()){
            // 当前新增字符
            char newChar = s.charAt(end-1);
            subStrCharCounts[newChar - 'a']++;
 
            // 判断当前子串是否符合要求
            // 如果新增字符导致子串中频次超出了p中频次，那么移动start，消除新增字符的影响
            while (subStrCharCounts[newChar - 'a'] > pCharCounts[newChar - 'a'] && start < end){
                char removeChar = s.charAt(start);
                subStrCharCounts[removeChar - 'a'] --;
                start ++;
            }
 
            // 如果当前子串长度等于p的长度，那么就是一个字母异位词
            if (end - start == p.length()){
                result.add(start);
            }
            end ++;
        }
        return result;
    }

复杂度分析

时间复杂度：O(|s|)。窗口的左右指针最多都到达 s 串结尾，s 串每个字符最多被左右指针都经过一次，所以时间复杂度为O(|s|)。

空间复杂度：O(1)。只需要两个大小为 26 的计数数组，大小均是确定的常量，所以空间复杂度为O(1)。

4.3 方法三：滑动窗口（双指针 2）


public List<Integer> findAnagrams(String s, String p) {  
    int s_len = s.length(), p_len = p.length();  
    List<Integer> ans = new ArrayList<Integer>();//用于记录窗口滑动过程中的可行解  
  
    //字符s的长度一定要大于字符p的长度，否则不存在异位词  
    if (s_len < p_len) {  
        return ans;  
    }  
    
    int[] window_count = new int[26]; //用于维护窗口滑动过程中每个字符的数量  
    int[] p_count = new int[26]; //用于统计字符p的每个字符数量  
    
    //初始统计  
    for (int i = 0; i < p_len; i++) {  
        window_count[s.charAt(i) - 'a']++;  
        p_count[p.charAt(i) - 'a']++;  
    }  
    
    //如果窗口最初始的时候满足异位词，则将0加入到ans数组中  
    if (Arrays.equals(window_count, p_count))  
        ans.add(0);  
        
    //窗口开始滑动,左右都按照同频率滑动  
    for (int i = 0; i < s_len - p_len; i++) {  
        window_count[s.charAt(i) - 'a']--;    // 左指针移动  
        window_count[s.charAt(i + p_len) - 'a']++;  // 右指针移动  
        
        //判断是否满足异位词的条件，满足加入到ans中  
        if (Arrays.equals(window_count, p_count))  
            ans.add(i + 1);  
            
    }  
    
    return ans;  
}

首先，根据输入的字符串 s 和 p，获取它们的长度，用 s_len 和 p_len 表示，并创建一个空的结果列表 ans。
检查如果字符串 s 的长度小于字符串 p 的长度，则不存在任何异位词，直接返回空的结果列表 ans。
创建两个长度为 26 的整数数组 window_count 和 p_count，用于记录窗口滑动过程中每个字符的数量以及字符 p 中每个字符的数量。这里使用了一个假设，即输入的字符串只包含小写字母。
进行初始统计：遍历字符串 p 的每个字符，将其在 window_count 和 p_count 数组中对应位置的计数值加1。
检查窗口最初始的时候是否满足异位词的条件，即 window_count 和 p_count 数组是否相等。如果相等，说明窗口的起始子串是与字符串 p 是异位词，将起始索引 0 添加到结果列表 ans 中。这里在滑动窗口的同时进行异位体校验，也是采取了双指针的方式。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/276904