hot100滑动窗口题解

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

问题描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

题解

以下是 无重复字符的最长子串 的 C++ 解法，采用滑动窗口算法，时间复杂度为 $O(n)$。

---

解题思路

1. 滑动窗口：
   • 使用两个指针 left 和 right，表示当前窗口的起点和终点。
   • 用一个哈希集合 set 存储窗口中的字符，确保字符不重复。
2. 窗口扩展和收缩：
   • 当窗口右侧 right 指向的字符未在集合中时，将其加入集合，并扩大窗口。
   • 当窗口右侧字符重复时，从窗口左侧开始移除字符（移动 left 指针），直到窗口不包含重复字符。
3. 记录最大长度：
   • 在每次扩展窗口后，更新最长无重复子串的长度。

---

C++ 代码实现

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> charSet; // 存储当前窗口中的字符
    int left = 0; // 滑动窗口的左指针
    int maxLength = 0; // 记录最长无重复子串的长度

    for (int right = 0; right < s.size(); ++right) {
        // 如果字符重复，收缩窗口
        while (charSet.count(s[right])) {
            charSet.erase(s[left]);
            ++left;
        }
        // 将当前字符加入集合并更新最大长度
        charSet.insert(s[right]);
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of Longest Substring: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

---

代码解析

1. 滑动窗口：
   • left 和 right 维护窗口的左右边界。
   • charSet 确保窗口中的字符不重复。
2. 窗口收缩：
   • 当窗口中出现重复字符时，通过移动 left 指针收缩窗口，直到窗口中不包含重复字符。
3. 更新最大长度：
   • 每次扩展窗口后，计算当前窗口长度 right - left + 1，并更新最大长度。

---

时间复杂度

1. 遍历字符串：
   • 每个字符最多进出集合一次，总时间复杂度为 $O(n)$。
2. 总复杂度：
   • $O(n)$。

---

空间复杂度

• 使用了一个集合存储窗口中的字符，最坏情况下需要 $O(n)$ 的空间。

---

示例运行

输入：

s = "abcabcbb"

输出：

3

解释：

最长无重复子串为 "abc"，其长度为 3。

---

总结

• 滑动窗口算法通过动态调整窗口范围，高效解决了无重复字符的最长子串问题。
• 时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

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

问题描述

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

示例 1:

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

示例 2:

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

提示:

• $1 <= s.length, p.length <= 3 * 10^4$
• s 和 p 仅包含小写字母

题解

要解决这道题，我们可以使用 滑动窗口 和 计数数组 的方法。以下是 C++ 语言的题解。

解题思路

1. 异位词的特性:
   • 两个字符串是异位词，当且仅当它们包含的字符及其频率相同。
2. 滑动窗口:
   • 使用滑动窗口，维护一个窗口，该窗口的大小等于字符串 p 的长度。
   • 对窗口内的字符频率进行统计，并与字符串 p 的字符频率进行比较。
3. 计数数组:
   • 使用两个大小为 26 的数组分别记录字符串 p 的字符频率和滑动窗口内的字符频率。
   • 每次滑动窗口时，更新窗口的频率统计，并检查是否匹配。
4. 复杂度:
   • 时间复杂度为 $O(n)$，因为每个字符至多被遍历两次。
   • 空间复杂度为 $O(1)$，因为计数数组大小固定。

C++ 实现代码

#include <vector>
#include <string>
#include <iostream>

using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    if (s.size() < p.size()) return result;

    vector<int> pCount(26, 0), windowCount(26, 0);

    // 统计字符串 p 的字符频率
    for (char c : p) {
        pCount[c - 'a']++;
    }

    // 初始化窗口内的字符频率
    for (int i = 0; i < p.size(); ++i) {
        windowCount[s[i] - 'a']++;
    }

    // 检查初始窗口是否匹配
    if (windowCount == pCount) result.push_back(0);

    // 滑动窗口
    for (int i = p.size(); i < s.size(); ++i) {
        // 添加当前字符到窗口
        windowCount[s[i] - 'a']++;
        // 移除窗口左端字符
        windowCount[s[i - p.size()] - 'a']--;

        // 检查窗口是否匹配
        if (windowCount == pCount) result.push_back(i - p.size() + 1);
    }

    return result;
}

int main() {
    string s = "cbaebabacd";
    string p = "abc";
    vector<int> result = findAnagrams(s, p);

    for (int index : result) {
        cout << index << " ";
    }
    return 0;
}

代码说明

1. 初始化字符频率数组:
   • 用 pCount 记录字符串 p 的字符频率。
   • 用 windowCount 记录当前滑动窗口内的字符频率。
2. 滑动窗口:
   • 初始窗口为字符串 s 的前 p.size() 个字符。
   • 每次滑动窗口时，更新 windowCount，添加新字符并移除旧字符。
   • 比较 windowCount 和 pCount，若相等则记录起始索引。
3. 返回结果:
   • 返回结果向量 result，其中包含所有满足条件的起始索引。

示例运行

输入:

s = "cbaebabacd", p = "abc"

输出:

0 6

输入:

s = "abab", p = "ab"

输出:

0 1 2

优化点

• 直接比较 windowCount 和 pCount 是 $O(26)$，即常数时间复杂度。
• 如果需要进一步优化，可以在滑动窗口时通过增量更新匹配状态，而不是每次比较整个数组。