242. 有效的字母异位词（Valid Anagram）
频次 ★★★ · 难度 🟢 · 高频：全厂
题目
给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词（两个字符串中每个字符的出现次数完全相同）。
示例：
输入: s = "anagram", t = "nagaram"
输出: true
输入: s = "rat", t = "car"
输出: false
说明：假设字符串只包含小写字母。
思路
字母异位词的本质是字符计数相同。因为限定小写字母（26 个），用一个 int[26] 数组当哈希表：遍历 s 时对应位置 +1，遍历 t 时对应位置 -1，最后检查数组是否全 0。全 0 说明两个字符串每个字符出现次数相同，互为异位词。
如果字符串包含 Unicode 字符（不限小写字母），改用 HashMap<Character, Integer>，思路不变。
代码
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) {
return false;
}
}
return true;
}复杂度
- 时间：O(n) — 两个字符串各遍历一次，最后检查 26 个位置是常数时间
- 空间：O(1) —
int[26]是固定大小，不随输入规模增长
边界条件
- 两个字符串长度不等：直接返回
false，不可能互为异位词 - 空字符串：两个空字符串互为异位词，计数数组全 0，返回
true - 包含重复字符：计数 +1/-1 抵消，只要所有字符出现次数相同即可
变式
- Unicode 字符版：用
HashMap<Character, Integer>代替int[26]，s字符 +1，t字符 -1，最后检查所有 value 是否为 0 - 只遍历一次计数数组：可以边遍历边维护一个
diff计数器（s 字符 +1 时若 count 从 0 变 1 则 diff++，t 字符 -1 时若 count 从 0 变 -1 则 diff++，反之则 diff—），最后判断 diff 是否为 0，省去最后检查 26 个位置的循环
易错点
- 不能只判断
s的字符都在t中出现——还要保证次数相同，如s="aab",t="abb"只判断存在性会误判 - 排序后比较字符串（
Arrays.sort）也是 O(n log n)，且需要额外空间存储排序结果，不如计数法 O(n) 高效 - 不能在循环外单独遍历
t再遍历s——两个循环分开写会多一次遍历且代码冗余；一次循环同时处理两个字符串的对应字符更简洁
面试追问
- 如果字符串包含 Unicode 字符怎么办？
int[26]不够用，改用HashMap<Character, Integer>，时间复杂度仍是 O(n)，空间变为 O(k)（k 为字符集大小）。进阶可以讨论int[128]（ASCII）和int[256]（扩展 ASCII）的适用场景。 - 计数法和排序法各有什么适用场景？ 计数法 O(n)/O(1) 适合小字符集；排序法 O(n log n) 实现简单，适合字符集很大但字符串很短的情况（此时 k 可能超过 n，计数法空间反而更大）。
关联题
- 同套路：49. 字母异位词分组 —— 本题是单对判断版，分组题是它的批量聚合
- 进阶：438. 找到字符串中所有字母异位词 —— 滑动窗口 + 计数，在长串中找所有异位词子串
- 知识点：哈希表 O(1) 查找的原理见集合框架