哈希表（典型算法思想）—— OJ例题算法解析思路

目录

一、1. 两数之和 - 力扣（LeetCode）

算法代码： 

1. 问题描述

2. 核心思路

3. 代码实现思路

（1）初始化哈希表

（2）遍历数组

（3）返回结果

4. 时间复杂度分析

5. 示例演示

输入：

执行过程：

输出：

6. 边界情况考虑

7. 代码总结

8. 代码优化（可选）

二、面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

算法代码： 

1. 问题描述

2. 核心思路

3. 代码实现思路

（1）长度检查

（2）初始化哈希表

（3）统计 s1 的字符频率

（4）检查 s2 的字符频率

（5）返回结果

4. 时间复杂度分析

5. 示例演示

输入：

执行过程：

输出：

6. 边界情况考虑

7. 代码总结

8. 代码优化（可选）

三、217. 存在重复元素 - 力扣（LeetCode）

算法代码： 

代码分析

1. 输入和输出

2. 哈希表的使用

3. 遍历数组

4. 检查重复

5. 返回结果

整体思路总结

时间与空间复杂度

举例说明

四、219. 存在重复元素 II - 力扣（LeetCode） 

算法代码： 

代码分析

1. 输入和输出

2. 哈希表的使用

3. 遍历数组

4. 检查重复和索引差

5. 更新哈希表

6. 返回结果

整体思路总结

时间与空间复杂度

举例说明

五、 49. 字母异位词分组 - 力扣（LeetCode）

算法代码： 

代码分析

1. 输入和输出

2. 哈希表的使用

3. 将字母异位词分组

4. 提取结果

5. 返回结果

整体思路总结

时间与空间复杂度

举例说明

---

一、1. 两数之和 - 力扣（LeetCode）

算法代码： 

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash; // <nums[i], i>for (int i = 0; i < nums.size(); i++) {int x = target - nums[i];if (hash.count(x))return {hash[x], i};hash[nums[i]] = i;}// 照顾编译器return {-1, -1};}
};

1. 问题描述

给定一个整数数组 nums 和一个目标值 target，要求在数组中找到两个数，使得它们的和等于 target，并返回这两个数的下标。

---

2. 核心思路

• 暴力解法：双重循环遍历所有可能的数对，检查它们的和是否等于 target。时间复杂度为 O(n2)O(n2)。

• 优化思路：利用哈希表存储已经遍历过的数及其下标，通过查找哈希表来快速判断是否存在满足条件的数对。

---

3. 代码实现思路

（1）初始化哈希表

unordered_map<int, int> hash; // <nums[i], i>

• 哈希表的键是数组中的元素值（nums[i]），值是该元素的下标（i）。

• 哈希表的作用是快速查找某个值是否已经存在于数组中。

（2）遍历数组

for (int i = 0; i < nums.size(); i++) {int x = target - nums[i];if (hash.count(x))return {hash[x], i};hash[nums[i]] = i;
}

• 步骤 1：计算目标差值 x = target - nums[i]。

  • 如果 x 存在于哈希表中，说明之前已经遍历过 x，且 x 的下标为 hash[x]。

  • 此时，nums[i] 和 x 就是满足条件的两个数，直接返回它们的下标 {hash[x], i}。

• 步骤 2：如果 x 不存在于哈希表中，将当前元素 nums[i] 及其下标 i 存入哈希表，以便后续查找。

（3）返回结果

• 如果找到满足条件的数对，直接返回它们的下标。

• 如果遍历结束后仍未找到，返回 {-1, -1}（这是一个默认值，用于照顾编译器，实际题目保证有解）。

---

4. 时间复杂度分析

• 时间复杂度：O(n)。

  • 遍历数组一次，每次查找哈希表的时间复杂度为 O(1)。

• 空间复杂度：O(n)。

  • 哈希表最多存储 n 个元素。

---

5. 示例演示

输入：

nums = [2, 7, 11, 15], target = 9

执行过程：

1. 初始化哈希表：hash = {}。

2. 遍历数组：

   • i = 0，nums[0] = 2，计算 x = 9 - 2 = 7。

     • 哈希表中没有 7，将 2 存入哈希表：hash = {2: 0}。

   • i = 1，nums[1] = 7，计算 x = 9 - 7 = 2。

     • 哈希表中有 2，返回 {hash[2], 1} = {0, 1}。

输出：

[0, 1]

---

6. 边界情况考虑

• 重复元素：如果数组中有重复元素，哈希表会存储最后一个出现的下标，但不会影响结果，因为题目保证只有一个解。

• 无解情况：题目保证有解，因此无需处理无解情况。如果题目不保证有解，可以在遍历结束后返回空数组或抛出异常。

---

7. 代码总结

• 核心思想：利用哈希表的快速查找特性，将两数之和问题从 O(n2)O(n2) 优化到 O(n)O(n)。

• 实现细节：

  • 哈希表存储元素值及其下标。

  • 遍历时计算目标差值，并在哈希表中查找。

  • 找到解后立即返回，避免不必要的遍历。

---

8. 代码优化（可选）

• 如果题目要求返回所有可能的解，可以将哈希表的值改为存储下标列表，并在找到解时记录所有满足条件的下标对。

• 如果数组已排序，可以使用双指针法，进一步优化空间复杂度为 O(1)O(1)。

二、面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

算法代码： 

class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size())return false;int hash[26] = {0};// 先统计第⼀个字符串的信息for (auto ch : s1)hash[ch - 'a']++;// 扫描第⼆个字符串，看看是否能重排for (auto ch : s2) {hash[ch - 'a']--;if (hash[ch - 'a'] < 0)return false;}return true;}
};

1. 问题描述

给定两个字符串 s1 和 s2，判断它们是否可以通过字符重排得到彼此。例如：

• s1 = "abc", s2 = "cba"，返回 true。

• s1 = "abc", s2 = "def"，返回 false。

---

2. 核心思路

• 变位词的定义：两个字符串的字符种类和数量完全相同，但顺序可以不同。

• 统计字符频率：通过哈希表（数组）统计每个字符的出现次数，然后比较两个字符串的字符频率是否一致。

---

3. 代码实现思路

（1）长度检查

if (s1.size() != s2.size())return false;

• 如果两个字符串的长度不同，直接返回 false，因为长度不同的字符串不可能是变位词。

（2）初始化哈希表

int hash[26] = {0};

• 使用一个长度为 26 的数组 hash 来统计字符频率。

• 数组的索引表示字符（'a' 到 'z'），值表示该字符的出现次数。

（3）统计 s1 的字符频率

for (auto ch : s1)hash[ch - 'a']++;

• 遍历 s1 的每个字符，将其映射到数组索引（ch - 'a'），并增加对应位置的计数。

（4）检查 s2 的字符频率

for (auto ch : s2) {hash[ch - 'a']--;if (hash[ch - 'a'] < 0)return false;
}

• 遍历 s2 的每个字符，将其映射到数组索引，并减少对应位置的计数。

• 如果某个字符的计数变为负数，说明 s2 中该字符的出现次数多于 s1，直接返回 false。

（5）返回结果

return true;

• 如果遍历结束后没有发现计数为负数的情况，说明两个字符串的字符频率完全一致，返回 true。

---

4. 时间复杂度分析

• 时间复杂度：O(n)，其中 nn 是字符串的长度。

  • 遍历 s1 和 s2 各一次，每次操作的时间复杂度为 O(1)O(1)。

• 空间复杂度：O(1)。

  • 使用固定大小的数组（长度为 26），与输入规模无关。

---

5. 示例演示

输入：

s1 = "anagram", s2 = "nagaram"

执行过程：

1. 长度检查：s1 和 s2 的长度均为 7，继续执行。

2. 统计 s1 的字符频率：

   • hash = {a: 3, n: 1, g: 1, r: 1, m: 1}。

3. 检查 s2 的字符频率：

   • 遍历 s2，每次减少对应字符的计数。

   • 遍历结束后，hash 中所有字符的计数均为 0。

4. 返回 true。

输出：

true

---

6. 边界情况考虑

• 空字符串：如果 s1 和 s2 都为空字符串，返回 true。

• 大小写敏感：代码假设字符串只包含小写字母。如果包含大写字母或其他字符，需要扩展哈希表的大小或使用 unordered_map。

• 非字母字符：如果字符串包含非字母字符（如数字、标点符号），需要调整哈希表的实现方式。

---

7. 代码总结

• 核心思想：通过哈希表统计字符频率，判断两个字符串的字符频率是否一致。

• 实现细节：

  • 使用数组模拟哈希表，适用于字符范围固定的场景。

  • 遍历时动态减少字符计数，避免额外的遍历操作。

---

8. 代码优化（可选）

• 如果字符串可能包含大写字母或其他字符，可以使用 unordered_map 代替数组：

  unordered_map<char, int> hash;
  for (auto ch : s1)hash[ch]++;
  for (auto ch : s2) {hash[ch]--;if (hash[ch] < 0)return false;
  }
  return true;

• 如果字符串长度较大，可以提前返回 false，避免不必要的遍历。

三、217. 存在重复元素 - 力扣（LeetCode）

算法代码： 

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for (auto x : nums)if (hash.count(x))return true;elsehash.insert(x);return false;}
};

代码分析

1. 输入和输出

• 输入: 一个整数数组 nums。

• 输出: 布尔值 true 或 false，分别表示数组中是否存在重复元素。

2. 哈希表的使用

unordered_set<int> hash;

• 创建一个 unordered_set<int> 类型的哈希表 hash，用于存储已经遍历过的元素。哈希表的查找和插入操作平均时间复杂度为 O(1)，使得这个方法高效。

3. 遍历数组

for (auto x : nums)

• 使用范围 for 循环遍历数组 nums 中的每个元素 x。

4. 检查重复

if (hash.count(x))return true; // 如果已存在，则返回 true
elsehash.insert(x); // 否则，将当前元素插入哈希表

• 在每次遍历时，使用 hash.count(x) 检查当前元素 x 是否已存在于哈希表中：

  • 如果存在，说明有重复元素，直接返回 true。

  • 如果不存在，将当前元素 x 插入哈希表中，以便在后续的遍历中进行检查。

5. 返回结果

return false;

• 如果循环结束后仍未发现重复元素，则返回 false。

整体思路总结

1. 初始化: 创建一个空的哈希表，用于存储已经检查过的元素。

2. 遍历元素: 逐一检查数组中的元素。

3. 检查存在性: 对每个元素，使用哈希表判断它是否已经出现过。

4. 处理结果:

   • 如果出现过，返回 true。

   • 如果遍历结束后未发现重复，返回 false。

时间与空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 nums 的长度。遍历数组的每个元素，每次查找和插入操作的平均时间复杂度为 O(1)。

• 空间复杂度: O(n)，在最坏的情况下，哈希表可能会存储数组中的所有元素。

举例说明

假设输入数组为 nums = [1, 2, 3, 1]。

1. 初始化哈希表 hash 为 {}。

2. 遍历第一个元素 1，hash.count(1) 返回 0，插入 1，现在 hash = {1}。

3. 遍历第二个元素 2，hash.count(2) 返回 0，插入 2，现在 hash = {1, 2}。

4. 遍历第三个元素 3，hash.count(3) 返回 0，插入 3，现在 hash = {1, 2, 3}。

5. 遍历第四个元素 1，hash.count(1) 返回 1，发现重复，返回 true。

如果输入为 nums = [1, 2, 3]，遍历结束后没有发现重复，返回 false。

四、219. 存在重复元素 II - 力扣（LeetCode） 

算法代码： 

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++) {if (hash.count(nums[i])) {if (i - hash[nums[i]] <= k)return true;}hash[nums[i]] = i;}return false;}
};

代码分析

1. 输入和输出

• 输入: 一个整数数组 nums 和一个整数 ( k )。

• 输出: 布尔值 true 或 false，分别表示是否存在满足条件的重复元素。

  

2. 哈希表的使用

unordered_map<int, int> hash;

• 创建一个 unordered_map<int, int> 类型的哈希表 hash，用于存储每个元素及其最近出现的索引。键为数组中的元素，值为该元素最后一次出现的索引。

3. 遍历数组

for (int i = 0; i < nums.size(); i++) {

• 使用一个 for 循环遍历数组 nums 中的每个元素。

4. 检查重复和索引差

if (hash.count(nums[i])) {if (i - hash[nums[i]] <= k)return true; // 找到满足条件的重复元素
}

• 在每次遍历时，检查当前元素 nums[i] 是否已经存在于哈希表中：

  • 如果存在，检查当前索引 ( i ) 与该元素最近索引（即 hash[nums[i]]）之间的差值是否小于或等于 ( k )。

  • 如果满足条件 ( i - hash[nums[i]] \leq k )，则返回 true，表示找到了满足条件的重复元素。

5. 更新哈希表

hash[nums[i]] = i;

• 无论该元素是否存在于哈希表中，都将当前元素 nums[i] 的索引 ( i ) 更新到哈希表中。这确保了每次我们都能得到当前元素的最新索引。

6. 返回结果

return false;

• 如果循环结束后仍未找到满足条件的重复元素，返回 false。

整体思路总结

1. 初始化: 创建一个哈希表 hash 来存储元素及其索引。

2. 遍历元素: 逐一遍历数组中的每个元素。

3. 检查存在性与条件:

   • 对于每个元素，检查其是否已经在哈希表中。

   • 如果在，计算该元素的当前索引与上次出现索引之间的差值是否小于或等于 ( k )。

   • 满足条件则返回 true。

4. 更新索引: 更新哈希表中该元素的最新索引。

5. 返回结果: 如果遍历结束未发现符合条件的重复元素，则返回 false。

时间与空间复杂度

• 时间复杂度: O(n)，其中 ( n ) 是数组 nums 的长度。对每个元素进行常数时间的查找和插入操作。

• 空间复杂度: O(min(n, k))，在最坏情况下，哈希表可能会存储最多 ( k ) 个不同的元素（如果数组中重复的元素分布在 ( k ) 个索引范围内），或者存储 ( n ) 个元素（如果所有元素都是不同的）。

举例说明

假设我们有一个数组 nums 为 [1, 2, 3, 1]，并且 ( k = 3 )。

1. 初始哈希表: hash 为 {}。

2. 遍历:

   • 索引 0: 元素 1，hash 变为 {1: 0}。

   • 索引 1: 元素 2，hash 变为 {1: 0, 2: 1}。

   • 索引 2: 元素 3，hash 变为 {1: 0, 2: 1, 3: 2}。

   • 索引 3: 元素 1，hash 中已存在 1，计算索引差：3 - 0 = 3，满足条件 ( |i - j| \leq k )，返回 true。

如果我们检查数组 nums = [1, 0, 1, 1]，并且 ( k = 1 )：

1. 初始化: hash 为 {}。

2. 遍历:

   • 索引 0: 1，hash 变为 {1: 0}。

   • 索引 1: 0，hash 变为 {1: 0, 0: 1}。

   • 索引 2: 1，hash 中已存在 1，计算差值：2 - 0 = 2，不满足 ( |i - j| \leq 1 )。

   • 索引 3: 1，再次找到 1，计算差值：3 - 0 = 3，仍然不满足条件，最终返回 false。

五、 49. 字母异位词分组 - 力扣（LeetCode）

算法代码： 

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;// 1. 把所有的字⺟异位词分组for (auto& s : strs) {string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}// 2. 结果提取出来vector<vector<string>> ret;for (auto& [x, y] : hash) {ret.push_back(y);}return ret;}
};

代码分析

1. 输入和输出

• 输入: 一个字符串数组 strs，其中包含多个字符串。

• 输出: 一个二维字符串数组 ret，其中每个子数组包含一组字母异位词。

  

2. 哈希表的使用

unordered_map<string, vector<string>> hash;

• 创建一个哈希表 hash，键为排序后的字符串，值为一个字符串向量，存储与该排序字符串相对应的原字符串列表。

3. 将字母异位词分组

for (auto& s : strs) {string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);
}

• 遍历输入的字符串数组 strs：

  • 对于每个字符串 s，创建一个临时字符串 tmp 并对其进行排序。排序后的字符串作为键，所有与该键对应的异位词存储在哈希表中。

  • 使用 hash[tmp].push_back(s) 将原字符串 s 加入哈希表中对应的向量。

4. 提取结果

vector<vector<string>> ret;
for (auto& [x, y] : hash) {ret.push_back(y);
}

• 创建一个二维向量 ret 用于存储最终的结果。

• 遍历哈希表，提取每个键 x 及其对应的值 y（即异位词组），并将每个值添加到结果向量 ret 中。

5. 返回结果

return ret;

• 返回包含所有字母异位词组的二维向量 ret。

整体思路总结

1. 初始化: 创建一个哈希表 hash 用于存储经过排序的字符串及其对应的原字符串，它将用于分组异位词。

2. 遍历输入字符串: 对于每个字符串，将其字母排序，使用排序后的字符串作为键，将原字符串存储到对应的值（向量）中。

3. 提取结果: 从哈希表中提取所有的异位词组并存储到结果向量中。

4. 返回结果: 返回分组后的异位词。

时间与空间复杂度

• 时间复杂度: O(N * K log K)，其中 ( N ) 是字符串数组的长度，( K ) 是字符串的平均长度。对于每个字符串，排序的时间复杂度是 O(K log K)，因此整体复杂度为 O(N * K log K)。

• 空间复杂度: O(N * K)，存储所有输入字符串的哈希表和结果向量占用的空间，最坏情况下需要存储所有字符串。

举例说明

假设输入字符串数组为 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]。

1. 初始化哈希表: hash 为 {}。

2. 遍历并分组:

   • 对于字符串 "eat"，排序后为 "aet"，哈希表更新为 { "aet": ["eat"] }。

   • "tea" 排序后仍为 "aet"，哈希表更新为 { "aet": ["eat", "tea"] }。

   • "tan" 排序后为 "ant"，哈希表更新为 { "aet": ["eat", "tea"], "ant": ["tan"] }。

   • "ate" 排序后为 "aet"，哈希表更新为 { "aet": ["eat", "tea", "ate"], "ant": ["tan"] }。

   • "nat" 排序后为 "ant"，哈希表更新为 { "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"] }。

   • "bat" 排序后为 "abt"，哈希表更新为 { "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"] }。

3. 提取结果: 从哈希表提取组，结果为：

   • ret 变为 [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]。

4. 返回结果:

   • 返回结果数组 ret。