哈希表_两数之和、判定是否为字符重排_C++【含哈希表使用场景】

---

0. 哈希表使用场景

---

1. 哈希表是什么？

• 存储数据的容器。

2. 有什么用？

• 能“快速”的查找某个元素，时间复杂度能达到O(1)。

3. 什么时候用？

• 频繁查找某个数时，使用哈希表。

4. 怎么用？

• 使用现成容器。
• 用数组模拟简易哈希表（更快）。
  • 需要查找字符时。字符可以当做索引。
  • 数据范围很小时（出现负数就不要用数组模拟了）。

---

1. 两数之和

---

leetcode链接：https://leetcode.cn/problems/two-sum/description/

1. 暴力解法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;for (int i = 0; i < nums.size(); i++){for (int j = i + 1; j < nums.size(); j++){if (nums[i] + nums[j] == target){ret.push_back(i);ret.push_back(j);}}}return ret;}
};

2. 哈希

• 从左向右遍历，一边遍历，一边让元素进入哈希表。
• 令x = target - nums[i]表示要找的值，如果该元素在哈希中出现过，直接返回num[i]和x这两个元素的下标，说明找到了。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++){int x = target - nums[i];if (hash.count(x)) return {hash[x], i};else hash[nums[i]] = i;}// 照顾编译器，leetcode要求非void函数必须有返回值return {-1, -1};}
};

---

2. 判定是否为字符重排

---

leetcode链接：https://leetcode.cn/problems/check-permutation-lcci/

思路：

• 分别为s1和s2创建哈希表，然后将比较哈希表中每个元素的数量即可。

class Solution {
public:bool CheckPermutation(string s1, string s2) {int hash1[26] = {0};int hash2[26] = {0};for (auto e : s1)hash1[e - 'a']++;for (auto e : s2)hash2[e - 'a']++;for (int i = 0; i < 26; i++){if (hash1[i] != hash2[i]) return false;}return true;}
};

---