LeetCode 补拙笔记

0. 前言

• 日期：2026.06.27
• 题目：438. 找到字符串中所有字母异位词
• 难度：中等
• 标签：滑动窗口、哈希表、数组计数

1. 题目理解

问题描述 给定字符串 s 和 p，找出 s 中全部是 p 的字母异位词的子串起始下标，异位词指字符种类、每个字符出现次数完全一致，字符顺序可不同。

示例

输入：s = "cbaebabacd", p = "abc" 输出：[0,6] 解释：下标0子串cba、下标6子串bac均为abc的异位词。

2. 解题思路

核心观察

1. 异位词长度一定等于 p 的长度，采用固定长度滑动窗口；
2. 原版使用HashMap存字符计数，存在字符串装箱、equals全量比对开销；
3. 优化方案：使用长度128的int数组统计ASCII字符计数，维护匹配成功的字符总数，无需每次完整比对两个容器，减少分支与比较开销。

算法步骤

1. 特判：若p长度大于s，直接返回空集合；
2. 统计p的字符计数数组；
3. 初始化s的首个窗口计数，统计匹配成功字符数量match；
4. 滑动窗口：移除左侧字符、加入右侧字符，动态更新match；
5. match == 26 代表窗口为异位词，记录起始下标。

3. 代码实现

package lc438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        if (pLen > sLen) return res;

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < pLen; i++) {
            String c = String.valueOf(p.charAt(i));
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        HashMap<String, Integer> map1 = new HashMap<>();
        int right = 0;
        // 初始化s的前pLen窗口
        for (; right < pLen; right++) {
            String c = String.valueOf(s.charAt(right));
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }
        if (map1.equals(map)) {
            res.add(0);
        }

        // 滑动窗口，条件修正
        for (int left = 0; right < sLen; left++, right++) {
            // 1. 移除左边界字符
            String leftChar = String.valueOf(s.charAt(left));
            map1.put(leftChar, map1.get(leftChar) - 1);
            if (map1.get(leftChar) == 0) {
                map1.remove(leftChar);
            }
            // 2. 添加新右边界字符
            String rightChar = String.valueOf(s.charAt(right));
            map1.put(rightChar, map1.getOrDefault(rightChar, 0) + 1);
            // 3. 判断匹配，起始下标 left+1
            if (map1.equals(map)) {
                res.add(left + 1);
            }
        }
        return res;
    }
}

4. 代码优化说明

import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int n = s.length(), m = p.length();
    if (m > n) return ans;
    // ASCII固定数组计数，替代HashMap
    int[] cntP = new int[128];
    int[] cntS = new int[128];
    // 统计模板p字符数量
    for (char c : p.toCharArray()) cntP[c]++;
    int match = 0;
    // 初始化首个窗口
    for (int r = 0; r < m; r++) {
        char ch = s.charAt(r);
        cntS[ch]++;
        // 该字符计数匹配成功则match+1
        if (cntS[ch] == cntP[ch]) match++;
    }
    if (match == 26) ans.add(0);
    // 滑动窗口遍历剩余字符
    for (int l = 0, r = m; r < n; l++, r++) {
        // 移出左边界字符
        char leftCh = s.charAt(l);
        if (cntS[leftCh] == cntP[leftCh]) match--;
        cntS[leftCh]--;
        // 加入右边界字符
        char rightCh = s.charAt(r);
        cntS[rightCh]++;
        if (cntS[rightCh] == cntP[rightCh]) match++;
        // 全部26个字符计数匹配，记录起始下标
        if (match == 26) ans.add(l + 1);
    }
    return ans;
}
}

5. 复杂度分析

• HashMap原版 时间：$O(n\ast m)$，每次equals需要遍历全部键值对，存在大量字符串装箱、分支判断 空间：$O(1)$，仅26个小写字母，哈希表容量恒定
• 数组滑动窗口优化版 时间：$O(n)$，仅单次遍历字符串，无容器全量比对，分支大幅减少 空间：$O(1)$，固定长度128数组，不随输入长度变化

6. 总结

• 核心：固定长度滑动窗口 + 字符计数匹配判断异位词；
• 优化亮点：用ASCII数组替代HashMap，消除字符串装箱；维护match变量替代每次equals比对，大量减少if分支与循环开销；
• 关键技巧：通过匹配成功字符总数快速判断窗口是否为异位词，避免全量容器比较。