滑动窗口技术

滑动窗口（Sliding Window）常用于处理数组或字符串的连续子问题。通过维护一个窗口的两端，避免了重复的嵌套遍历。

3. 无重复字符的最长子串 (Longest Substring Without Repeating Characters)

题目描述

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

解题思路

使用两个指针表示窗口。利用哈希表记录字符及其出现的最新索引。如果字符已存在于窗口中，则将左边界移动到其上一次出现位置的下一位。

Java 代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (map.containsKey(ch)) {
                left = Math.max(left, map.get(ch) + 1);
            }
            map.put(ch, right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

---

438. 找到字符串中所有字母异位词 (Find All Anagrams in a String)

题目描述

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

解题思路

维护一个长度为 p.length() 的固定滑动窗口。使用数组分别记录窗口内字符频次。如果频次相同，说明找到了一个异位词。

Java 代码实现

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sn = s.length(), pn = p.length();
        if (sn < pn) return new ArrayList<>();
        int[] scount = new int[26], pcount = new int[26];
        for (int i = 0; i < pn; i++) {
            scount[s.charAt(i) - 'a']++; pcount[p.charAt(i) - 'a']++;
        }
        List<Integer> res = new ArrayList<>();
        if (Arrays.equals(scount, pcount)) res.add(0);
        for (int i = 0; i < sn - pn; i++) {
            scount[s.charAt(i) - 'a']--;
            scount[s.charAt(i + pn) - 'a']++;
            if (Arrays.equals(scount, pcount)) res.add(i + 1);
        }
        return res;
    }
}