数组与哈希简单3 种解法

#242有效的字母异位词

判断两个字符串是否由完全相同的字符及出现次数组成。

#哈希表#字符串#排序

解题主线

长度不同可立即失败；本质是比较字符频次多重集。

字符集固定为 26 个小写字母时，定长数组优于通用映射。

解法 1：通用字符频次表

累计 s 的 UTF-16 字符单元频次，再用 t 逐项抵消并删除归零项。

时间复杂度

O(n) 期望

空间复杂度

O(k)，k 为不同字符数

242. 有效的字母异位词 · 通用字符频次表

java

import java.util.HashMap;
import java.util.Map;

final class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.merge(c, 1, Integer::sum);
        for (char c : t.toCharArray()) {
            Integer count = counts.get(c);
            if (count == null) return false;
            if (count == 1) counts.remove(c);
            else counts.put(c, count - 1);
        }
        return counts.isEmpty();
    }
}

累计 s 的 UTF-16 字符单元频次，再用 t 逐项抵消并删除归零项。

解法 2：排序后比较

字符排序后，异位词应得到完全相同的字符序列。

时间复杂度

O(n log n)

空间复杂度

O(n)，字符数组与排序栈

242. 有效的字母异位词 · 排序后比较

java

import java.util.Arrays;

final class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        Arrays.sort(first);
        Arrays.sort(second);
        return Arrays.equals(first, second);
    }
}

字符排序后，异位词应得到完全相同的字符序列。

解法 3：26 位计数数组

对 s 的字符加一、对 t 的字符减一，最终所有位置必须为零。

时间复杂度

O(n)

空间复杂度

O(1)

242. 有效的字母异位词 · 26 位计数数组

java

final class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        for (int count : counts) {
            if (count != 0) return false;
        }
        return true;
    }
}

对 s 的字符加一、对 t 的字符减一，最终所有位置必须为零。

合并 Q242 与误放在 Q349 中的同一计数实现。

边界与易错点

26 长度数组只适用于题目限定的小写英文字母；扩展字符集应改用 Map。
Q349 文件中混入的 isAnagram3 属于本题，已与 Q242 合并，不算 Q349 的第二种解法。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q242_isAnagram.javaeasy/Q349_intersection.java