1100.md

【中规中矩】1100. 长度为 K 的无重复字符子串(三种语言实现滑动窗口）

解题思路

滑动所有长度为K的窗口，查看当时hash表的大小恰好为K则自增1即可。

代码

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        int res = 0;
        if (S.size() < K) {
            return 0;
        }

        unordered_map<char, int> mp;
        for (int i = 0; i < K; i++) {
            mp[S[i]]++;
        }

        if (mp.size() == K) {
            res++;
        }

        for (int i = K; i < S.size(); i++) {
            mp[S[i]]++;
            mp[S[i - K]]--;
            if (mp[S[i - K]] == 0) {
                mp.erase(S[i - K]);
            }

            if (mp.size() == K) {
                res++;
            }
        }

        return res;
    }
};

class Solution {
    public int numKLenSubstrNoRepeats(String S, int K) {
        // 和无重复最长的子串类似，使用滑动窗口
        int length = S.length();

        int res = 0;
        int left = 0; 
        Map<Character, Integer> window = new HashMap<>();
        for (int right = 0; right < length; right++) {
            char ch = S.charAt(right);
            window.put(ch, window.getOrDefault(ch, 0) + 1);
            // 添加的无重复，且窗口长度为K, 则累加，并将窗口整体右移，继续判断后面的
            if (window.get(ch) == 1 && (right - left + 1 == K)) {
                res++;
                window.put(S.charAt(left), window.get(S.charAt(left)) - 1);
                left++;
                continue;
            }

            // 有重复则整体右移，直到把重复的那个给排除在外
            while (window.get(ch) > 1) {
                window.put(S.charAt(left), window.get(S.charAt(left)) - 1);
                left++;
            }

        }

        return res;
    }
}

class Solution(object):
    def numKLenSubstrNoRepeats(self, S, K):
        n = len(S)
        res = 0
        for i in range(n - K  + 1):
            tmp = set(S[i : i + K])
            if (len(tmp) == K):
                res += 1

        return res

点我赞赏作者

github 题解