leetcode——哈希表1

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 

字母异位词

。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

原理

1. 字母异位词定义：

   • 字母异位词（Anagram）是指两个字符串中，字符的种类和每个字符的出现次数完全相同，但字符的顺序可以不同。

2. 思路：

   • 首先，字母异位词的核心在于判断两个字符串的字符集合是否完全相同。因此，我们可以通过统计两个字符串中每个字符的出现次数来比较它们。

3. 步骤：

   • 创建两个数组 mapS 和 mapT：这两个数组的长度固定为 26（因为只有 26 个小写字母）。数组 mapS 用于记录字符串 s 中每个字符的出现次数，数组 mapT 用于记录字符串 t 中每个字符的出现次数。
   • 遍历字符串 s 和 t：通过字符的 ASCII 值来定位字符在数组中的位置，然后更新数组中的对应位置。
     • 例如，字符 'a' 对应的索引是 s.charAt(j) - 'a'，即 0，字符 'b' 对应的索引是 1，依此类推。
   • 比较两个数组 mapS 和 mapT：最终，我们遍历这两个数组，逐个位置进行比较。如果某个位置的字符频次不相同，则返回 false，表示这两个字符串不是字母异位词。如果所有位置的频次都相同，则返回 true。

4. 时间复杂度：

   • 遍历两个字符串的时间复杂度为 O(n)，其中 n 是字符串的长度。
   • 遍历两个数组 mapS 和 mapT 的时间复杂度是 O(26)，即常数时间。
   • 因此，总时间复杂度为 O(n)，其中 n 是字符串的长度。

5. 空间复杂度：

   • 我们只使用了两个固定大小的数组 mapS 和 mapT，它们的空间复杂度是 O(1)（因为它们的大小是常数 26）。
   • 总的空间复杂度是 O(1)。

进阶：处理 Unicode 字符

• 如果输入字符串包含 Unicode 字符（不仅限于小写字母），你可以考虑使用一个哈希表（如 HashMap）来存储字符的频次，而不是使用固定大小的数组。
• 你可以将字符作为键，字符的出现次数作为值。这样可以处理所有类型的字符，而不仅限于小写字母。

代码 

class Solution {public boolean isAnagram(String s, String t) {// 创建两个数组，用来存储字符串s和t中各个字符出现的次数int[] mapS = new int[26];  // mapS 用于存储字符串s的字符频次int[] mapT = new int[26];  // mapT 用于存储字符串t的字符频次// 遍历字符串s，更新mapS中各个字符的频次for (int j = 0; j < s.length(); j++) {mapS[s.charAt(j) - 'a']++;  // 根据字符的ASCII值减去'a'来确定数组的索引}// 遍历字符串t，更新mapT中各个字符的频次for (int j = 0; j < t.length(); j++) {mapT[t.charAt(j) - 'a']++;  // 同上，更新mapT数组}// 比较mapS和mapT数组的值，检查两个字符串的字符频次是否完全相同for (int j = 0; j < 26; j++) {if (mapS[j] != mapT[j]) {  // 如果在某个位置上的频次不同，返回falsereturn false;}}// 如果所有频次都相同，则返回true，表示t是s的字母异位词return true;}
}

 38.赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

原理

该问题的目标是判断 ransomNote 中的每个字符是否都能从 magazine 中找出对应字符，且每个字符在 magazine 中只能使用一次。

步骤：

1. 字符计数：

   • 由于题目限制字符串只包含小写字母，我们可以用一个长度为 26 的数组 mapM 来记录 magazine 中每个字母的出现次数。
   • magazine 中的每个字符通过 magazine.charAt(i) - 'a' 转换为数组索引，从而更新该字符的计数。

2. 判断是否可以构建 ransomNote：

   • 遍历 ransomNote 中的每个字符，并从 mapM 中减去对应字符的计数，表示我们“使用”了 magazine 中的一个字符。
   • 如果在这个过程中，某个字符的计数变为负数，说明 magazine 中的字符数量不足，无法满足 ransomNote 中该字符的需求，因此返回 false。

3. 最终判断：

   • 如果遍历完 ransomNote 后，没有出现负数的情况，说明 magazine 中有足够的字符来构建 ransomNote，返回 true。

时间复杂度：

• 统计 magazine 字符的频次需要遍历一次 magazine，时间复杂度为 O(m)，其中 m 是 magazine 的长度。
• 遍历 ransomNote 来检查字符计数需要遍历一次 ransomNote，时间复杂度为 O(n)，其中 n 是 ransomNote 的长度。
• 最后，我们遍历 26 个字母来检查是否有负数，时间复杂度为 O(26)，这是一个常数操作。
• 因此，总的时间复杂度为 O(m + n)，其中 m 和 n 分别是 magazine 和 ransomNote 的长度。

空间复杂度：

• 使用了一个长度为 26 的数组 mapM 来存储字符的频次，空间复杂度是 O(1)，因为数组的大小是常数。
• 总的空间复杂度是 O(1)。

代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 创建一个长度为26的数组mapM，用于存储magazine中每个字母的出现次数int[] mapM = new int[26];// 遍历magazine，统计每个字符的出现次数for (int i = 0; i < magazine.length(); i++) {mapM[magazine.charAt(i) - 'a']++;  // 通过字符减去'a'得到字符的索引，更新字符的计数}// 遍历ransomNote，尝试从mapM中减去字符的计数for (int i = 0; i < ransomNote.length(); i++) {mapM[ransomNote.charAt(i) - 'a']--;  // 将ransomNote中的每个字符从magazine中对应字符的计数中减去}// 遍历mapM数组，检查是否有任何位置的值为负for (int i = 0; i < 26; i++) {if (mapM[i] < 0) {  // 如果某个字符的计数小于0，说明magazine中的字符不足以构成ransomNotereturn false;  // 返回false，表示无法构造ransomNote}}// 如果所有字符的计数都大于或等于0，表示magazine可以构造ransomNotereturn true;  // 返回true}
}

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

原理

该问题的目标是找到字符串 s 中所有与 p 是字母异位词的子串的位置。字母异位词是由相同字母组成但顺序不同的字符串，因此我们可以通过字符的频次来判断两个字符串是否为字母异位词。

解决思路：

1. 字符频次编码：

   • 字母异位词的核心在于它们的字符频次相同。因此，我们为每个字符串（包括 p 和 s 的子串）计算其字符频次并生成一个编码。
   • 这里使用一个大小为 26 的数组（code）来存储字符串中每个字符的频次。字符的频次数组最终转化为一个字符串，作为该字符串的“编码”。

2. 滑动窗口：

   • 对于字符串 s，我们使用滑动窗口技术来获取长度为 p.length() 的子串。每次滑动一个字符位置，将窗口内的子串进行编码，并与 p 的编码进行比较。
   • 如果某个子串的编码与 p 的编码相同，说明这个子串与 p 是字母异位词，将该子串的起始位置记录下来。

3. HashMap 用于存储编码和位置：

   • 使用一个 HashMap（anagrams）来存储每个编码对应的子串起始位置的列表。encode() 方法将字符串转化为字符频次编码，并将编码作为键存入 anagrams。
   • 对于每个长度为 p.length() 的子串，如果它的编码与 p 的编码相同，就将该子串的起始位置加入 anagrams 中。

4. 返回结果：

   • 在遍历 s 后，返回 p 的编码对应的所有子串的起始位置列表。

时间复杂度：

• 计算字符串 p 的编码需要 O(m)，其中 m 是 p 的长度。
• 遍历字符串 s 时，我们每次从 s 中提取长度为 m 的子串，并计算它的编码。每次计算编码的时间复杂度是 O(m)。
• 因此，总的时间复杂度为 O(n * m)，其中 n 是 s 的长度，m 是 p 的长度。

空间复杂度：

• 用于存储字符频次的数组 code 的大小为常数 26，因此空间复杂度是 O(1)。
• 使用 HashMap 存储编码和位置列表，最坏情况下，s 中的每个子串都可能有一个不同的编码，所以 HashMap 的大小为 O(n)，其中 n 是 s 的长度。

代码 

class Solution {public List<Integer> findAnagrams(String s, String p) {// 创建一个 HashMap 来存储每个编码对应的位置列表HashMap<String, List<Integer>> anagrams = new HashMap<>();// 如果 s 的长度小于 p 的长度，则不可能有字母异位词，直接返回空列表if (s.length() < p.length()) {return new ArrayList<>();}// 对字符串 p 进行编码，并将其存储到 anagrams 中，确保编码存在String p1 = encode(p, p.length());anagrams.putIfAbsent(p1, new ArrayList<>());// 遍历字符串 s，检查每个长度为 p.length() 的子串for (int i = 0; i < s.length() - p.length() + 1; i++) {// 获取当前子串的编码String s1 = encode(s.substring(i, i + p.length()), p.length());// 将当前子串的编码放入 anagrams 中，如果编码不存在就初始化一个空列表anagrams.putIfAbsent(s1, new ArrayList<>());// 将当前子串的起始位置加入对应的编码列表中anagrams.get(s1).add(i);}// 返回 p 的编码对应的位置列表return anagrams.get(p1);}// 编码函数：将字符串的字符频次转化为固定大小的字符串（长度为26）public String encode(String str, int len) {// 创建一个长度为 26 的字符频次数组char[] code = new char[26];// 遍历字符串的每个字符，更新对应字符的频次for (int i = 0; i < len; i++) {code[str.charAt(i) - 'a']++;}// 将字符频次数组转换为字符串作为编码return String.valueOf(code);}
}

438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 

异位词

 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

原理

该问题要求我们找到字符串 s 中所有与字符串 p 字母异位词相同的子串的起始索引。字母异位词是指两个字符串含有相同的字符，但字符的顺序不同。可以通过字符频次的方式来判断两个字符串是否是字母异位词。

解决思路：

1. 编码转换：

   • 字母异位词的核心在于它们的字符频次相同，因此我们可以对字符串 p 及 s 中的每个长度为 p.length() 的子串计算字符频次，并将其转化为一个“编码”。
   • 这里使用一个大小为 26 的数组（code）来记录字符的频次。字符的频次数组最终转化为一个字符串，作为该字符串的“编码”。

2. 滑动窗口：

   • 我们使用滑动窗口技术来获取字符串 s 中所有长度为 p.length() 的子串。
   • 每当滑动窗口向右移动时，我们检查当前窗口中的子串是否与 p 是字母异位词。通过对该子串进行编码并与 p 的编码进行比较，判断它们是否相等。
   • 如果它们的编码相等，说明当前子串是字母异位词，我们将该子串的起始索引记录下来。

3. 使用 HashMap 存储编码和位置：

   • 我们使用一个 HashMap（anagrams）来存储每个编码对应的子串起始位置列表。encode() 方法将字符串转化为字符频次编码，并将编码作为键存入 anagrams。
   • 对于每个长度为 p.length() 的子串，计算其编码并与 p 的编码进行比较。如果它们相等，说明该子串是 p 的字母异位词，将该子串的起始位置加入 anagrams 中。

4. 返回结果：

   • 最后，我们返回 p 的编码对应的所有子串的起始位置列表，即返回所有字母异位词的位置。

时间复杂度：

• 对于字符串 s 中的每个长度为 p.length() 的子串，计算其字符频次编码的时间复杂度是 O(m)，其中 m 是 p 的长度。
• 遍历字符串 s 时，我们每次滑动窗口并计算子串的编码，这样的操作共进行 n - m + 1 次，其中 n 是 s 的长度。
• 因此，总的时间复杂度是 O(n * m)，其中 n 是 s 的长度，m 是 p 的长度。

空间复杂度：

• 用于存储字符频次的数组 code 的大小为常数 26，因此空间复杂度是 O(1)。
• 使用 HashMap 存储编码和位置列表，最坏情况下，s 中的每个子串都可能有一个不同的编码，所以 HashMap 的大小为 O(n)，其中 n 是 s 的长度。

代码 

class Solution {public List<Integer> findAnagrams(String s, String p) {// 创建一个 HashMap 用于存储编码与对应的子串起始索引HashMap<String, List<Integer>> anagrams = new HashMap<>();// 如果 s 的长度小于 p 的长度，无法找到字母异位词，直接返回空列表if (s.length() < p.length()) {return new ArrayList<>();}// 对字符串 p 进行编码，生成一个固定的字符频次表示String p1 = encode(p, p.length());// 确保 p 的编码在 anagrams 中存在anagrams.putIfAbsent(p1, new ArrayList<>());// 遍历字符串 s，获取每个长度为 p.length() 的子串for (int i = 0; i < s.length() - p.length() + 1; i++) {// 获取当前子串的编码String s1 = encode(s.substring(i, i + p.length()), p.length());// 确保当前子串编码在 anagrams 中存在anagrams.putIfAbsent(s1, new ArrayList<>());// 将当前子串的起始位置添加到对应编码的列表中anagrams.get(s1).add(i);}// 返回 p 的编码对应的子串起始位置列表return anagrams.get(p1);}// 编码函数：将字符串转换为一个字符频率数组的字符串表示public String encode(String str, int len) {// 创建一个长度为 26 的数组，用于记录字符的频次char[] code = new char[26];// 遍历字符串中的每个字符，更新字符的频次for (int i = 0; i < len; i++) {code[str.charAt(i) - 'a']++;}// 将字符频次数组转换为字符串并返回return String.valueOf(code);}
}

这题其实不用hash，能更好的解决，其实是滑动窗口的思想，滑动窗口能把时间复杂度降低到o(n)

原理

该问题要求我们在字符串 s 中找到所有的字母异位词子串的起始索引。字母异位词是由相同字母组成，但字母的顺序可以不同。可以通过字符的频次来判断两个字符串是否是字母异位词。

解决思路：

1. 字符频次差异：

   • 我们使用一个长度为 26 的数组 code 来记录 s 和 p 中各个字母的频次差异。通过在遍历过程中对字符频次的增减，来判断当前窗口内的子串是否与 p 是字母异位词。

2. 滑动窗口：

   • 我们使用滑动窗口技术来遍历字符串 s 中的每个长度为 p.length() 的子串。
   • 对于每一个字符，更新对应频次数组中的计数，并检查当前窗口中的字符频次是否与 p 完全匹配。
   • 如果字符频次数组中的所有值均为0，说明当前子串与 p 是字母异位词，并将其起始位置记录下来。

3. 更新字符频次：

   • 每次滑动窗口时，当前窗口右端字符的频次会被减1，表示该字符被当前窗口包含。
   • 然后，检查当前窗口是否是字母异位词，如果是，就记录下当前窗口的起始位置。
   • 滑动窗口后，移出窗口左端字符时，我们需要恢复该字符的频次。

4. 判断字母异位词：

   • 通过 IsAnagrams 方法检查字符频次数组是否全为0，如果是，说明该子串是字母异位词。

时间复杂度：

• 遍历字符串 s 的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。
• 每次遍历时，我们需要检查一个长度为 26 的字符频次数组，IsAnagrams 方法的时间复杂度是 O(26) ≈ O(1)，因此可以认为是常数时间操作。
• 总的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。

空间复杂度：

• 使用一个大小为 26 的数组 code 来存储字符频次，因此空间复杂度是 O(1)，因为数组大小固定。
• 使用一个列表 anagrams 存储所有字母异位词的起始位置，空间复杂度为 O(k)，其中 k 是找到的字母异位词的数量。
• 因此，总的空间复杂度是 O(k)。

代码

class Solution {public List<Integer> findAnagrams(String s, String p) {// 创建一个长度为26的数组用于存储字符频次差异int[] code = new int[26];// 创建一个列表用于存储结果：所有字母异位词的起始索引List<Integer> anagrams = new ArrayList<>();// 遍历字符串 p，更新字符频次（将 p 中的每个字符计数加1）for (int i = 0; i < p.length(); i++) {code[p.charAt(i) - 'a']++;  // 更新 p 中字符的频次}// 遍历字符串 s，检查每个长度为 p.length() 的子串是否是字母异位词for (int i = 0; i < s.length(); i++) {// 更新当前字符的频次（s 中的字符频次减1）code[s.charAt(i) - 'a']--;// 如果当前字符频次数组符合字母异位词条件（即所有字符的频次均为0），// 说明当前子串是 p 的字母异位词，将其起始位置加入结果列表if (IsAnagrams(code) == true) {anagrams.add(i + 1 - p.length());  // 记录当前子串的起始索引}// 如果 i+1-p.length() >= 0，则恢复上一个字符的频次（滑动窗口移动）if (i + 1 - p.length() >= 0) {code[s.charAt(i + 1 - p.length()) - 'a']++;}}return anagrams;  // 返回所有字母异位词的起始索引列表}// 判断当前字符频次数组是否为字母异位词的条件：如果所有元素为0，则是字母异位词public boolean IsAnagrams(int[] array) {// 遍历频次数组，检查是否每个字符的频次均为0for (int i = 0; i < 26; i++) {if (array[i] != 0) {return false;  // 如果有任何一个字符的频次不为0，说明不是字母异位词}}return true;  // 所有字符的频次为0，说明是字母异位词}
}