面试经典 150 题-滑动窗口

LeetCode 面试经典 150 题-滑动窗口

长度最小的子数组

前缀和+滑动窗口

子数组不是子序列，不能去掉一些数字，它必须是连续的。考虑求数组的前缀和，前缀和数组一定是飞递减的，因为数组中的数字都是大于0的。然后遍历前缀和数组，维护一个滑动窗口，如果当前和小于目标，则滑动窗口的右指针右移扩大窗口，否则左指针右移缩小窗口，同时更新最短子数组长度。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        // 计算前缀和
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i-1] + nums[i-1];
        }
        // 滑动窗口
        int left = 0, right = 0;
        int ans = n + 1;
        while(right <= n) {
            if (prefix[right] - prefix[left] >= target) {
                ans = Math.min(ans, right - left);
                left++;
            } else {
                right++;
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化空间复杂度

空间复杂度可以优化，一边计算前缀和，一边收缩边界。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int sum = 0;
        // 滑动窗口
        int left = 0;
        int ans = n + 1;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            // 更新左边界
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

无重复字符的最长子串

哈希表+滑动窗口

用一个哈希表记录当前窗口内的字符情况。如果右指针向右移动扩大窗口范围不会造成重复字符出现，那么就扩展，否则移动左指针至窗口内不含重复字符，同时更新最大长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int[] hash = new int[128];
        int left = 0, ans = 0;

        for (int right = 0; right < n; right++) {
            int ch = s.charAt(right);
            // 扩展窗口
            hash[ch]++;
            // 保证没有重复字符
            while (hash[ch] > 1) {
                hash[s.charAt(left)]--;
                left++;
            }
            // 更新最大长度
            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

• 时间复杂度：O(n)，每个字符最多被移入和移出一次。
• 空间复杂度：$O(|\Sigma|)$，所有 ASCII 码在 [0,128) 内的字符。

也可以用bool类型代替int，因为只需要判断有没有出现过，不需要知道有几个。也可以用hashset。

串联所有单词的子串

哈希表+滑动窗口

1. 初始化
   • res：存储结果的列表。
   • m：单词列表 words 的长度，即单词的个数。
   • n：单词的长度（假设 words 中的单词长度一致）。
   • ls：字符串 s 的长度。
2. 外层循环：遍历从 0 到 n-1 的索引，利用滑动窗口处理子串，并确保窗口起点与单词长度对齐。
3. 滑动窗口初始化
   • 在滑动窗口的初始范围内，统计窗口中单词的频率并存入 differ。
   • 对比 differ 和 words，将 words 中的单词频率从 differ 中减去，得到初始的频率差异。
4. 滑动窗口更新
   • 每次窗口向右滑动一个单词的长度，更新窗口中新增和移除的单词频率。
   • 如果 differ 为空，则说明当前窗口内的子串满足条件，记录起始索引。
5. 返回结果：返回所有满足条件的起始索引

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 初始化
        int m = words.length, n = words[0].length(), ls = s.length();
        List<Integer> res = new ArrayList<>();

        // 外层循环，确保窗口起点与单词长度对齐
        for (int i = 0; i < n; i++) {
            // 超出字符串长度的起始位置无需处理
            if (i + m * n > ls) {
                break;
            }
            // 窗口中单词的频率并存入 differ
            Map<String, Integer> differ = new HashMap<String, Integer>();
            for (int j = 0; j < m; j++) {
                String word = s.substring(i + j * n, i + (j + 1) * n);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            // 对比 differ 和 words，将 words 中的单词频率从 differ 中减去
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            // 滑动窗口更新，每次窗口向右滑动一个单词的长度
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    // 加入向右滑动的一个单词
                    String word = s.substring(start + (m-1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    // 去掉左边被滑出的单词
                    word = s.substring(start - n, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                // 如果频次差异为空，则说明是一个串联子串
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }
}

• 时间复杂度：O(ls×n)，其中 ls 是输入 s 的长度，n 是 words 中每个单词的长度。需要做 n 次滑动窗口，每次需要遍历一次 s。
• 空间复杂度：O(m×n)，其中 m 是 words 的单词数，n 是 words 中每个单词的长度。每次滑动窗口时，需要用一个哈希表保存单词频次。

这道题有点难，以后再好好想一想。

最小覆盖子串

哈希表+滑动窗口

维护一个哈希表，记录字符串t的情况。滑动窗口，同时再维护一个哈希表。移动右指针，更新哈希表情况，查看能否覆盖，判断涵盖t可以使用两个数组分别统计当前s和t的字符数情况，然后每次逐个字符判断，这样每次都要花费 O(∣Σ∣) 的时间去判断是否涵盖。因此可以用一个变量less代替，即目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数。若不能则继续移动右指针，否则移动左指针。

1. 初始化左右指针。
2. 用一个哈希表统计t的字符情况。
3. 初始化left，并用一个哈希表统计s的情况。
4. 初始化 less 为 t 中的不同字母个数。
5. 遍历 s，设当前枚举的子串右端点为 right，把字母 c=s[right] 的出现次数加一。加一后，如果 cntS[c]=cntT[c]，说明 c 的出现次数满足要求，把 less 减一。
   如果 less=0，说明 cntS 中的每个字母及其出现次数都大于等于 cntT 中的字母出现次数，那么：
   • 更新最短子串长度；
   • 滑动窗口左边界右移，更新cntS和less。
   • 重复上述步骤直至less>0.
6. 如果 ansLeft<0，说明没有找到符合要求的子串，返回空字符串，否则返回下标 ansLeft 到下标 ansRight 之间的子串。
7. 可以把 cntS 和 cntT 合并成一个 cnt，定义cnt[x]=cntT[x]−cntS[x]。

class Solution {
    public String minWindow(String s, String t) {
        // 初始化
        int m = s.length();
        int n = t.length();
        int[] cnt = new int[128];
        int less = 0;
        int ansLeft = -1, ansRight = m;
        for (int i = 0; i < n; i++) {
            // 统计不同字母数
            if (cnt[t.charAt(i)] == 0) {
                less++;
            }
            // 更新哈希表
            cnt[t.charAt(i)]++;
        }

        // 遍历 s，滑动窗口
        int left = 0;
        for (int right = 0; right < m; right++) {
            char ch = s.charAt(right);
            // 更新哈希表和less
            cnt[ch]--;
            if (cnt[ch] == 0) {
                less--;
            }
            // 如果涵盖，滑动左边界
            while (less == 0) {
                // 更新结果
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }
                // 更新哈希表
                cnt[s.charAt(left)]++;
                // 更新less
                if (cnt[s.charAt(left)] > 0) {
                    less++;
                }
                left++;
            } 
        }
        
        return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight + 1);
    }
}

• 时间复杂度：O(m + n)
• 空间复杂度：$O(|\Sigma|)$

总结

滑动窗口的题目通常与双指针和哈希表相关联，以后要多加复习。