hot100-滑动窗口

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

思路：双指针指向不含重复字符的连续字串的头和尾，用集合存储子串中的元素，有重复时，左指针持续右移，无重复后统计长度

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0; // 左边界
        int j = 0; // 右边界
        int n = s.length();
        int len = 0; // 记录最长不重复子串的长度
        if(n == 0){
            return 0;
        }
        // 使用 HashSet 来存储当前窗口内的字符，用于快速判断字符是否重复
        Set<Character> set = new HashSet<>();
​
        while(j < n){
            // 如果当前字符已经在窗口内，说明出现了重复字符
            // 需要移动左边界 i，直到窗口内没有重复字符为止
            while(set.contains(s.charAt(j))){
                set.remove(s.charAt(i));
                ++i;
            }
​
            len = Math.max(j - i, len);
            set.add(s.charAt(j));
            ++j;
        }
        // 因为在循环中计算长度时没有加 1，所以这里需要加 1
        return len + 1;
    }
}

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

思路：维护一个固定长度的窗口，向后遍历，每前进一步就检查当前窗口是否满足条件，满足条件就记录下来

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 获取字符串 s 和 p 的长度
        int sLen = s.length(), pLen = p.length();
​
        // 如果 s 的长度小于 p 的长度，直接返回空列表
        // 因为 s 中不可能包含 p 的字母异位词
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
​
        // 初始化结果列表，用于存储所有字母异位词的起始索引
        List<Integer> ans = new ArrayList<Integer>();
​
        // 初始化两个数组，分别用于统计 s 和 p 中字符的频率
        int[] sCount = new int[26]; // 统计 s 中字符的频率
        int[] pCount = new int[26]; // 统计 p 中字符的频率
​
        // 初始化窗口，统计 s 的前 pLen 个字符和 p 中所有字符的频率
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a']; // 统计 s 的前 pLen 个字符
            ++pCount[p.charAt(i) - 'a']; // 统计 p 中的所有字符
        }
​
        // 检查初始窗口是否是 p 的字母异位词
        // 如果两个频率数组相等，则说明 s 的前 pLen 个字符是 p 的字母异位词
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0); // 将起始索引 0 添加到结果列表中
        }
​
        // 使用滑动窗口遍历 s，窗口大小固定为 pLen
        for (int i = 0; i < sLen - pLen; ++i) {
            // 更新窗口：
            // 1. 移除窗口左边界字符的计数
            --sCount[s.charAt(i) - 'a'];
            // 2. 添加窗口右边界字符的计数
            ++sCount[s.charAt(i + pLen) - 'a'];
​
            // 检查当前窗口是否是 p 的字母异位词
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1); // 如果是，将当前窗口的起始索引添加到结果列表中
            }
        }
​
        // 返回结果列表
        return ans;
    }
}