哈希表基础
一般哈希表都是用来快速判断一个元素是否出现集合里。
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
- 数组
- set (集合)
- map(映射)
242 有效的字母异位词 Valid Anagram
要点
学习哈希表解题。哈希值比较小且范围比较可控的时候，选择使用数组解决。数值很大的时候，一般使用 set。k v 的时候使用 map。
此题中，字母均为小写字母，总共 26 个，可以开辟一个长为 26 的数组。数组的每一个位置储存对应字母在字符串中出现的个数。遍历第一个字符串，把每个位置的字符存进数组（使用 hash[s[i] - 'a'] 的方式获取 ASCII 码）
代码
时间复杂度 O(N) 空间复杂度 O(1)
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# if length not equal, cannot be anagram
if len(s) != len(t):
return False
# use list to store alphabet
hash_list = [0 for _ in range(26)]
for i in range(len(s)):
hash_list[ord(s[i]) - ord('a')] += 1
hash_list[ord(t[i]) - ord('a')] -= 1
for i in range(26):
if hash_list[i] != 0:
return False
return True
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
//int hash_array[26] = {0};
vector<int> hash_array(26);
for (int i = 0; i < s.size(); i++) {
hash_array[s[i] - 'a']++;
hash_array[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (hash_array[i] != 0) return false;
}
return true;
}
};
349 两个数组的交集 Intersection of Two Arrays
要点
- 此题里，数组的取值范围比字母表的略大一些。可以考虑使用 set 来做哈希表，由于限制在了 1000 以内，所以数组依旧可以做。两种方法都可以选取。
-
unordered_set::find()返回一个指向目标的指针；若未找到，则返回末尾指针unordered_set.end();
代码
set / unordered_map
时间复杂度 O(MN) (每次在set里查找需要M，总共N轮) 空间复杂度 O(N)
Python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_set = set(nums1)
res_set = set()
for num in nums2:
if num in nums1_set:
res_set.add(num)
return list(res_set)
C++
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
unordered_set<int> res_set;
for (int num : nums2) {
if (nums1_set.find(num) != nums1_set.end()) {
res_set.insert(num);
}
}
return vector<int>(res_set.begin(), res_set.end());
}
};
array / list
由于数值限制范围，所以使用数组时间复杂度更低。
时间复杂度 O(M+N) 空间复杂度 O(N) (给 set 的空间)
C++
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int nums1_hash[1001] = {0}; // to store 0 ~ 1000
unordered_set<int> res_set;
for (int num : nums1) {
nums1_hash[num] = 1;
}
for (int num : nums2) {
if (nums1_hash[num] == 1) {
res_set.insert(num);
}
}
return vector<int>(res_set.begin(), res_set.end());
}
};
Python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_list = [0 for _ in range(1001)]
res_set = set()
for num in nums1:
nums1_list[num] = 1
for num in nums2:
if nums1_list[num] == 1:
res_set.add(num)
return list(res_set)
202 快乐数 Happy Number
要点
- 注意使用辅助函数的时候，按位处理数字的办法：对 10 取模，再更新
n。 - 题意里提示
while True循环。关注if, else if, else对应的情况：如果n等于一，则直接为True，如果n不等于一，要看它是否在集合内，如果在，退出循环return False，若不在，则把它加入集合，再使用辅助函数更新一次n。
代码
时间复杂度 O(logN) 空间复杂度 O(logN)
Python
class Solution:
def isHappy(self, n: int) -> bool:
tmp_set = set()
while True:
if n == 1:
return True
elif n in tmp_set:
return False
else:
tmp_set.add(n)
n = self.getSum(n)
def getSum(self, n: int) -> int:
n_sum = 0
while n > 0:
n_sum += (n % 10) * (n % 10)
n //= 10
return n_sum
C++
class Solution:
def isHappy(self, n: int) -> bool:
tmp_set = set()
while True:
if n == 1:
return True
elif n in tmp_set:
return False
else:
tmp_set.add(n)
n = self.getSum(n)
def getSum(self, n: int) -> int:
n_sum = 0
while n > 0:
n_sum += (n % 10) * (n % 10)
n //= 10
return n_sum
1 两数之和 Two Sum
要点
- 使用
unordered_map，保存 k v 对。其中注意思考 k v 分别是什么：k 是 数组中的值，v 是对应的下标。 - 注意别忘了如果找不到，在最后返回一个空数组
return {}。
代码
时间复杂度 O(N) 遍历一次数组 空间复杂度 O(N) map 存储
C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> nums_map;
for (int i = 0; i < nums.size(); i++) {
int tmp = target - nums[i];
auto iter = nums_map.find(tmp);
if (iter != nums_map.end()) { // found it
return vector<int> {iter->second, i};
} else { // cannot find it, store in map
nums_map.insert(pair<int, int>(nums[i], i));
}
}
return {};
}
};
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for i in range(len(nums)):
tmp = target - nums[i]
if tmp in nums_dict.keys():
return [nums_dict[tmp], i]
else:
nums_dict[nums[i]] = i
return []
