滑动窗口

---

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

// 滑动窗口，l和r开始都从左开始，r往右遍历，如果窗口存在当前字符，l缩小窗口
// map记录了每个字符的下标，两个关键步骤分别是:更新l的值以及.put进行覆盖
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        HashMap<Character, Integer> map = new HashMap<>();

        for (int l = 0, r = 0; r < s.length(); r++) {
            char cur = s.charAt(r);
            if (map.containsKey(cur)) {
                // 这里需要取较大值，示例abba，不在窗口中的cur不算数
                l = Math.max(l, map.get(cur) + 1);
            }
            map.put(cur, r);
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

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

// 滑动窗口大小固定，移除左端添加右端
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 滑动窗口大小固定为p.length()，移除最左端，再添加最右端
        List<Integer> ans = new ArrayList<>();
        int len1 = s.length(), len2 = p.length();
        if (len1 < len2) {
            return ans;
        }
        // 两个数组记录前n个元素的字母出现次数
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < len2; i++) {
            cnt1[s.charAt(i) - 'a']++;
            cnt2[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(cnt1, cnt2)) {
            ans.add(0);
        }
        // 移除最左端的i，末尾添加i+n
        for (int i = 0; i < len1 - len2; i++) {
            cnt1[s.charAt(i) - 'a']--;
            cnt1[s.charAt(i + len2) - 'a']++;
            if (Arrays.equals(cnt1, cnt2)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}