[LC]1100. 长度为 K 的无重复字符子串

🚩传送门：牛客题目

题目

给你一个字符串 ，找出所有长度为 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。

示例 1：

输入：S = “havefunonleetcode”, K = 5 输出：6 解释： 这里有 6 个满足题意的子串，分别是：’havef’,’avefu’,’vefun’,’efuno’,’etcod’,’tcode’。

解题思路：集合判重

利用 set 进行判重，如果 set 中元素个数等于 说明没有重复元素

我的代码

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        HashSet<Character> set = new HashSet<>();
        int n=s.length();
        int res=0;
        for (int i = 0; i <= n-k; i++) {
            for (int j = 0; j < k; j++) {
                set.add(s.charAt(i+j));
            }
            // 说明无重复
            if(set.size()==k) res++;
            set.clear();
        }
        return res;
    }
}

解题思路：滑动窗口

利用 进行判重，当遇到冲突的时候，清除掉 区域，滑动窗口，从 处开始继续向下遍历，直至满足大小

我的代码

import java.util.HashMap;
class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        HashMap<Character, Integer> map = new HashMap<>();
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 如果发生冲突
            if (map.containsKey(s.charAt(i))) {
                int back = map.get(s.charAt(i)) + 1;
                // 清除窗口[f,b]区域
                for (int j = i - map.size(); j < back; j++) {
                    map.remove(s.charAt(j));
                }
                // 添加i 
                map.put(s.charAt(i), i);
            } else {
                // 未冲突记录i
                map.put(s.charAt(i), i);
            }
            if (map.size() == k) {
                res++;
                // 清除K窗口起点的map
                map.remove(s.charAt(i - k + 1));
            }
        }
        return res;
    }
}