LeetCode 热题 100-滑动窗口

无重复字符的最长子串

滑动窗口

使用哈希表+滑动窗口。如果当前字符没有在哈希表中出现过，就将其加入哈希表，右指针继续向右，right-left+1是当前长度，不断更新最大长度；否则不断向右滑动左窗口，直至遇到哈希表内没有当前元素，再把当前元素加入哈希表。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        // 处理边界
        if(n == 0 || n == 1){
            return n;
        }
        // 定义左右指针
        unordered_map<char, int> hash;
        int left = 0, right = 0;
        int ans = 0;

        while(right < n){
            // 如果没有出现过
            if(hash.find(s[right]) == hash.end()){
                hash[s[right]] = 1;
            }else{
                hash[s[right]]++;
            }
            // 移动左指针直至没有重复元素
            while(hash[s[right]] > 1){
                hash[s[left]]--;
                left++;
            }
            // 更新最大长度
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

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

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

定长滑动窗口

假设p的长度为n，枚举s的所有长为n的子串，如果该子串字母出现次数与p相同，则说明它是p的异位词，可以加入结果集。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = p.length();
        vector<int> ans;
        array<int, 26> cntP{};
        array<int, 26> cntS{};
        for(char ch : p){
            cntP[ch - 'a']++;
        }

        // 滑动窗口
        for(int right = 0; right < s.length(); right++){
            // 更新窗口内的哈希值
            cntS[s[right] - 'a']++;
            int left = right - n + 1;
            // 窗口长度不足
            if(left < 0){
                continue;
            }
            // 判断是否是异位词
            if(cntS == cntP){
                ans.push_back(left);
            }
            cntS[s[left] - 'a']--;  // 移动左指针
        }
        return ans;
    }
};

• 时间复杂度：O(∣Σ∣m+n)
• 空间复杂度：O(∣Σ∣)

不定长滑动窗口

枚举子串的右端点，如果其中一种字母的出现次数大于p的这种字母的出现次数，则右移子串的左端点。如果子串的长度等于p的长度，则说明子串的每种字母的出现次数，和 p 的每种字母的出现次数都相同，因为（如果出现次数 s 的小于 p 的，不可能长度一样）

代码实现时，可以把 cntS 和 cntP 合并成一个 cnt：

• 对于 p 的字母 c，把 cnt[p] 加一。
• 对于 s′的字母 c，把 cnt[c] 减一。
• 如果 cnt[c]<0，说明窗口中的字母 c 的个数比 p 的多，右移左端点。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int m = s.length();
        int n = p.length();
        // 统计p出现次数
        int cnt[26]{};
        for(char ch : p){
            cnt[ch - 'a']++;
        }
        // 滑动窗口
        int left = 0;
        for(int right = 0; right < m; right++){
            // 更新出现次数
            char ch = s[right] - 'a';
            cnt[ch]--;
            // 当前字母出现次数过多
            while(cnt[ch] < 0){
                cnt[s[left] - 'a']++;
                left++;
            }
            // 子串和p长度相等
            if(right - left + 1 == n){
                ans.push_back(left);
            }
        }
        return ans;
    }
};

• 时间复杂度：O(m + n)
• 空间复杂度：O(∣Σ∣)

补充知识

C++中的数组类型是继承了c语言的特性，在使用数组的时候要注意数组越界操作问题。为了更安全的对数组进行操作，C++提出了数组模板类array。array内存空间为连续的一段地址，适用于提前已知所要存储的数据类型和数量、进行大量的查、改操作，不适用于含有大量交换、删除、增加数据的操作，该容器无法动态改变大小，所以说提前已知存储数据类型和数量。