题解 | #长度为 K 的重复字符子串#

1.暴力

窗口滑动, 遍历每个区间，判断是否有重复字符

int numKLenSubstrRepeats(string s, int k) {
        int ans = 0;
        //O(n*k)
        for(int i=0; i<=s.length()-k; i++){
            int j=i+k-1;
            if(check(s, i, j))ans++;
        }
        return ans;
}
    bool check(string s, int l, int r) {
        unordered_map<char, int>umap;
        for (int i = l; i <= r; i++) {
            if (umap.count(s[i]))return true;
            umap[s[i]] = i;
        }
        return false;
    }

2.方法1改进

1. map记录窗口内每个字符出现的次数
2. 用一个变量 记录 重复字符的种数
3. 移进的字符， 字符数+1， 移出的字符， 字符数-1， 该字符数从 1->2 重复数+1 ，反之 -1
4. 判断重复字符的种数 是否=0， 等于0意味着区间内没有重复字符 否则 结果+1

int numKLenSubstrRepeats(string s, int k) {
        // write code here
        int ans = 0;
        map<char, int>umap;
        int res = 0;
        for (int i = 0; i < k; i++) {
            umap[s[i]]++;
            if (umap[s[i]] == 2) {
                res++;
            }
        }
        ans += res == 0 ? 0 : 1;

        for (int i = 1; i <= s.length() - k; i++) {
            int j = i + k - 1;
            umap[s[j]]++;
            if (umap[s[j]] == 2) {
                res++;
            }
            umap[s[i - 1]]--;
            if (umap[s[i - 1]] == 1)res--;
            ans += res == 0 ? 0 : 1;
        }
        return ans;
}