目录

算法----滑动窗口

框架

最小覆盖子串（力扣76）

字符串的排列（力扣567）

找字符串的异位词（力扣438）

最长无重复子串（力扣3）

重复的DNA序列（力扣187）

---

算法----滑动窗口

框架

1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？

2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？

3、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    unordered_map window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...
​
        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
​

最小覆盖子串（力扣76）

string minWindow(string s, string t) {
    unordered_map need, window;
    for (char c : t) need[c]++;
​
    int left = 0, right = 0;
    int valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }
​
        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ?
        "" : s.substr(start, len);
}
​

字符串的排列（力扣567）

// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map need, window;
    for (char c : t) need[c]++;
​
    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }
​
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}
​

找字符串的异位词（力扣438）

vector findAnagrams(string s, string t) {
    unordered_map need, window;
    for (char c : t) need[c]++;
​
    int left = 0, right = 0;
    int valid = 0;
    vector res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}
​

最长无重复子串（力扣3）

int lengthOfLongestSubstring(string s) {
    unordered_map window;
​
    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        window[c]++;
        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}
​

重复的DNA序列（力扣187）

List findRepeatedDnaSequences(String s) {
    // 先把字符串转化成四进制的数字数组
    int[] nums = new int[s.length()];
    for (int i = 0; i < nums.length; i++) {
        switch (s.charAt(i)) {
            case 'A':
                nums[i] = 0;
                break;
            case 'G':
                nums[i] = 1;
                break;
            case 'C':
                nums[i] = 2;
                break;
            case 'T':
                nums[i] = 3;
                break;
        }
    }
    // 记录重复出现的哈希值
    HashSet seen = new HashSet<>();
    // 记录重复出现的字符串结果
    HashSet res = new HashSet<>();
    
    // 数字位数
    int L = 10;
    // 进制
    int R = 4;
    // 存储 R^(L - 1) 的结果
    int RL = (int) Math.pow(R, L - 1);
    // 维护滑动窗口中字符串的哈希值
    int windowHash = 0;
    
    // 滑动窗口代码框架，时间 O(N)
    int left = 0, right = 0;
    while (right < nums.length) {
        // 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）
        windowHash = R * windowHash + nums[right];
        right++;
​
        // 当子串的长度达到要求
        if (right - left == L) {
            // 根据哈希值判断是否曾经出现过相同的子串
            if (seen.contains(windowHash)) {
                // 当前窗口中的子串是重复出现的
                res.add(s.substring(left, right));
            } else {
                // 当前窗口中的子串之前没有出现过，记下来
                seen.add(windowHash);
            }
            // 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）
            windowHash = windowHash - nums[left] * RL;
            left++;
        }
    }
    // 转化成题目要求的 List 类型
    return new LinkedList<>(res);
}
​

Rabin-Karp 算法

// Rabin-Karp 指纹字符串查找算法
int rabinKarp(String txt, String pat) {
    // 位数
    int L = pat.length();
    // 进制（只考虑 ASCII 编码）
    int R = 256;
    // 取一个比较大的素数作为求模的除数
    long Q = 1658598167;
    // R^(L - 1) 的结果
    long RL = 1;
    for (int i = 1; i <= L - 1; i++) {
        // 计算过程中不断求模，避免溢出
        RL = (RL * R) % Q;
    }
    // 计算模式串的哈希值，时间 O(L)
    long patHash = 0;
    for (int i = 0; i < pat.length(); i++) {
        patHash = (R * patHash + pat.charAt(i)) % Q;
    }
    
    // 滑动窗口中子字符串的哈希值
    long windowHash = 0;
    
    // 滑动窗口代码框架，时间 O(N)
    int left = 0, right = 0;
    while (right < txt.length()) {
        // 扩大窗口，移入字符
        windowHash = ((R * windowHash) % Q + txt.charAt(right)) % Q;
        right++;
​
        // 当子串的长度达到要求
        if (right - left == L) {
            // 根据哈希值判断是否匹配模式串
            if (windowHash == patHash) {
                // 当前窗口中的子串哈希值等于模式串的哈希值
                // 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
                if (pat.equals(txt.substring(left, right))) {
                    return left;
                }
            }
            // 缩小窗口，移出字符
            windowHash = (windowHash - (txt.charAt(left) * RL) % Q + Q) % Q;
            // X % Q == (X + Q) % Q 是一个模运算法则
            // 因为 windowHash - (txt[left] * RL) % Q 可能是负数
            // 所以额外再加一个 Q，保证 windowHash 不会是负数
​
            left++;
        }
    }
    // 没有找到模式串
    return -1;
}
​

参考：东哥的刷题秘籍 嘎嘎好用