:数组 + 字符串专项（算法基础载体，入门必刷）136. 只出现一次的数字 242. 有效的字母异位词)
136. 只出现一次的数字位运算异或^class Solution { public int singleNumber(int[] nums) { int t 0; // 初始化结果变量为 0利用性质 1 for (int num : nums) { // 遍历数组中每个数字 t ^ num; // 依次与当前数字异或等价于 t t ^ num } return t; // 最终 t 即为只出现一次的数字 } }核心逻辑异或运算的性质异或运算^有三个关键性质是解法的核心任何数与 0 异或结果为自身a ^ 0 a任何数与自身异或结果为 0a ^ a 0满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b哈希表统计频率import java.util.HashMap; import java.util.Map; class Solution { public int singleNumber(int[] nums) { // 1. 创建哈希表Key 为数组中的数字Value 为该数字出现的次数 MapInteger, Integer countMap new HashMap(); // 2. 第一次遍历统计每个数字出现的频率 for (int num : nums) { // getOrDefault如果 map 中已有 num则取出其值1否则默认值为 0 再加 1 countMap.put(num, countMap.getOrDefault(num, 0) 1); } // 3. 第二次遍历查找哈希表中值为 1 的 Key即只出现一次的数字 for (Map.EntryInteger, Integer entry : countMap.entrySet()) { if (entry.getValue() 1) { return entry.getKey(); } } // 题目规定非空且必有解此处仅为满足编译要求实际不会执行到 return -1; } }代码逐行解释MapInteger, Integer countMap new HashMap();定义一个哈希表键Key存储数组中的数字值Value存储该数字出现的次数。countMap.put(num, countMap.getOrDefault(num, 0) 1);这是统计频率的经典写法countMap.getOrDefault(num, 0)尝试从 map 中获取当前数字num的计数。如果num不存在返回默认值0。 1将计数加 1无论是第一次出现还是第 N 次出现。put(...)将更新后的计数重新存入 map。for (Map.EntryInteger, Integer entry : countMap.entrySet())遍历哈希表的每一组键值对Entry。entry.getKey()是数字entry.getValue()是它出现的次数。两种解法对比特性位运算法 (解法一)哈希表法 (解法二)时间复杂度O(n)O(n)空间复杂度O(1)(最优)O(n)通用性仅适用于 “其他数出现 2 次”适用于任何频率统计场景可读性需要了解位运算特性直观易懂逻辑清晰242. 有效的字母异位词排序class Solution { public boolean isAnagram(String s, String t) { // 1. 先判断长度是否相等不相等直接返回false if(s.length()!t.length()){ return false; } // 2. 将字符串转换为字符数组方便排序 char[] str s.toCharArray(); char[] str1 t.toCharArray(); // 3. 对两个字符数组分别排序 Arrays.sort(str); Arrays.sort(str1); // 4. 比较排序后的数组是否完全一致 return Arrays.equals(str, str1); } }复杂度分析时间复杂度O(nlogn)其中 n 是字符串长度。主要耗时在Arrays.sort()基于快速排序或归并排序时间复杂度为 O(nlogn)。空间复杂度O(n)。需要额外的字符数组存储字符串内容Java 中toCharArray()会创建新数组。优化降低时间复杂度字符串仅包含小写英文字母可以用数组计数的方法将时间复杂度降到 O(n)class Solution { public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } // 用长度为26的数组记录每个字母出现的次数 int[] count new int[26]; // 遍历s对应字母计数1 for (char c : s.toCharArray()) { count[c - a]; } // 遍历t对应字母计数-1 for (char c : t.toCharArray()) { count[c - a]--; // 如果计数为负说明t中有s没有的字符 if (count[c - a] 0) { return false; } } return true; } }扩展场景处理 Unicode 字符如果字符串包含Unicode 字符如中文、特殊符号可以用HashMap替代数组进行计数// 导入HashMap必须写在类外面 import java.util.HashMap; class Solution { // 核心方法判断s和t是否为字母异位词 public boolean isAnagram(String s, String t) { // 步骤1基础剪枝必写 // 长度不同直接不可能是字母异位词返回false if (s.length() ! t.length()) { return false; } // 步骤2创建哈希表 // Key字符CharacterValue该字符出现的次数Integer HashMapCharacter, Integer countMap new HashMap(); // 步骤3统计字符串s的字符频率 // 遍历s的每一个字符 for (char c : s.toCharArray()) { // getOrDefault(c, 0)如果map里有c返回对应次数没有就返回0 // 然后次数1重新存入map countMap.put(c, countMap.getOrDefault(c, 0) 1); } // 步骤4用字符串t抵消频率 for (char c : t.toCharArray()) { // 对应字符次数-1重新存入map countMap.put(c, countMap.getOrDefault(c, 0) - 1); // 关键如果计数0说明t有s中没有/数量更少的字符直接返回false if (countMap.get(c) 0) { return false; } } // 步骤5最终验证 // 所有字符次数都被抵消为0 → 是字母异位词 return true; } }核心思路底层逻辑字母异位词的本质两个字符串的「每个字符出现次数」完全一致。基于这个本质我们用HashMap 统计字符频率遍历第一个字符串记录每个字符出现了几次遍历第二个字符串把对应字符的计数减 1若所有字符最终计数都为 0 → 是字母异位词若中途出现负数 → 直接判定不是提前退出效率更高。关键知识点精讲新手必看1.getOrDefault方法核心countMap.getOrDefault(c, 0)作用安全获取哈希表中的值避免空指针异常逻辑如果字符c已经在 map 里 → 返回它的计数如果字符c不在 map 里 → 返回默认值0这是统计字符频率最简洁的写法。2. 提前剪枝if (countMap.get(c) 0)一旦某个字符计数变负说明t 包含 s 没有的字符或t 中该字符数量比 s 多直接返回false不用遍历完整个字符串提升效率。对比总结方法时间复杂度空间复杂度适用场景排序法原始代码O(nlogn)O(n)代码简洁小数据量场景数组计数法O(n)O(1)仅小写 / 大写英文字母HashMap 计数法O(n)O(k)所有字符通用最优解
Leetcode力扣零基础刷题快速入门指南(可用于备赛算法比赛):数组 + 字符串专项（算法基础载体，入门必刷）136. 只出现一次的数字 242. 有效的字母异位词
发布时间：2026/5/26 10:48:19
136. 只出现一次的数字位运算异或^class Solution { public int singleNumber(int[] nums) { int t 0; // 初始化结果变量为 0利用性质 1 for (int num : nums) { // 遍历数组中每个数字 t ^ num; // 依次与当前数字异或等价于 t t ^ num } return t; // 最终 t 即为只出现一次的数字 } }核心逻辑异或运算的性质异或运算^有三个关键性质是解法的核心任何数与 0 异或结果为自身a ^ 0 a任何数与自身异或结果为 0a ^ a 0满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b哈希表统计频率import java.util.HashMap; import java.util.Map; class Solution { public int singleNumber(int[] nums) { // 1. 创建哈希表Key 为数组中的数字Value 为该数字出现的次数 MapInteger, Integer countMap new HashMap(); // 2. 第一次遍历统计每个数字出现的频率 for (int num : nums) { // getOrDefault如果 map 中已有 num则取出其值1否则默认值为 0 再加 1 countMap.put(num, countMap.getOrDefault(num, 0) 1); } // 3. 第二次遍历查找哈希表中值为 1 的 Key即只出现一次的数字 for (Map.EntryInteger, Integer entry : countMap.entrySet()) { if (entry.getValue() 1) { return entry.getKey(); } } // 题目规定非空且必有解此处仅为满足编译要求实际不会执行到 return -1; } }代码逐行解释MapInteger, Integer countMap new HashMap();定义一个哈希表键Key存储数组中的数字值Value存储该数字出现的次数。countMap.put(num, countMap.getOrDefault(num, 0) 1);这是统计频率的经典写法countMap.getOrDefault(num, 0)尝试从 map 中获取当前数字num的计数。如果num不存在返回默认值0。 1将计数加 1无论是第一次出现还是第 N 次出现。put(...)将更新后的计数重新存入 map。for (Map.EntryInteger, Integer entry : countMap.entrySet())遍历哈希表的每一组键值对Entry。entry.getKey()是数字entry.getValue()是它出现的次数。两种解法对比特性位运算法 (解法一)哈希表法 (解法二)时间复杂度O(n)O(n)空间复杂度O(1)(最优)O(n)通用性仅适用于 “其他数出现 2 次”适用于任何频率统计场景可读性需要了解位运算特性直观易懂逻辑清晰242. 有效的字母异位词排序class Solution { public boolean isAnagram(String s, String t) { // 1. 先判断长度是否相等不相等直接返回false if(s.length()!t.length()){ return false; } // 2. 将字符串转换为字符数组方便排序 char[] str s.toCharArray(); char[] str1 t.toCharArray(); // 3. 对两个字符数组分别排序 Arrays.sort(str); Arrays.sort(str1); // 4. 比较排序后的数组是否完全一致 return Arrays.equals(str, str1); } }复杂度分析时间复杂度O(nlogn)其中 n 是字符串长度。主要耗时在Arrays.sort()基于快速排序或归并排序时间复杂度为 O(nlogn)。空间复杂度O(n)。需要额外的字符数组存储字符串内容Java 中toCharArray()会创建新数组。优化降低时间复杂度字符串仅包含小写英文字母可以用数组计数的方法将时间复杂度降到 O(n)class Solution { public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } // 用长度为26的数组记录每个字母出现的次数 int[] count new int[26]; // 遍历s对应字母计数1 for (char c : s.toCharArray()) { count[c - a]; } // 遍历t对应字母计数-1 for (char c : t.toCharArray()) { count[c - a]--; // 如果计数为负说明t中有s没有的字符 if (count[c - a] 0) { return false; } } return true; } }扩展场景处理 Unicode 字符如果字符串包含Unicode 字符如中文、特殊符号可以用HashMap替代数组进行计数// 导入HashMap必须写在类外面 import java.util.HashMap; class Solution { // 核心方法判断s和t是否为字母异位词 public boolean isAnagram(String s, String t) { // 步骤1基础剪枝必写 // 长度不同直接不可能是字母异位词返回false if (s.length() ! t.length()) { return false; } // 步骤2创建哈希表 // Key字符CharacterValue该字符出现的次数Integer HashMapCharacter, Integer countMap new HashMap(); // 步骤3统计字符串s的字符频率 // 遍历s的每一个字符 for (char c : s.toCharArray()) { // getOrDefault(c, 0)如果map里有c返回对应次数没有就返回0 // 然后次数1重新存入map countMap.put(c, countMap.getOrDefault(c, 0) 1); } // 步骤4用字符串t抵消频率 for (char c : t.toCharArray()) { // 对应字符次数-1重新存入map countMap.put(c, countMap.getOrDefault(c, 0) - 1); // 关键如果计数0说明t有s中没有/数量更少的字符直接返回false if (countMap.get(c) 0) { return false; } } // 步骤5最终验证 // 所有字符次数都被抵消为0 → 是字母异位词 return true; } }核心思路底层逻辑字母异位词的本质两个字符串的「每个字符出现次数」完全一致。基于这个本质我们用HashMap 统计字符频率遍历第一个字符串记录每个字符出现了几次遍历第二个字符串把对应字符的计数减 1若所有字符最终计数都为 0 → 是字母异位词若中途出现负数 → 直接判定不是提前退出效率更高。关键知识点精讲新手必看1.getOrDefault方法核心countMap.getOrDefault(c, 0)作用安全获取哈希表中的值避免空指针异常逻辑如果字符c已经在 map 里 → 返回它的计数如果字符c不在 map 里 → 返回默认值0这是统计字符频率最简洁的写法。2. 提前剪枝if (countMap.get(c) 0)一旦某个字符计数变负说明t 包含 s 没有的字符或t 中该字符数量比 s 多直接返回false不用遍历完整个字符串提升效率。对比总结方法时间复杂度空间复杂度适用场景排序法原始代码O(nlogn)O(n)代码简洁小数据量场景数组计数法O(n)O(1)仅小写 / 大写英文字母HashMap 计数法O(n)O(k)所有字符通用最优解
