【算法】代码随想录之哈希表（更新中）

文章目录

前言

一、有效的字母异位词（LeetCode--242）

二、两个数组的交集（LeetCode--349）

---

前言

跟随代码随想录，学习哈希表相关的算法题目，记录学习过程中的tips。

---

一、有效的字母异位词（LeetCode--242）

【1】题目描述：

【2】解决思想：哈希表中记录每个字母的个数。遍历s字符串，遇到一个字母就使哈希表对应位置+1。遍历t字符串，遇到一个字母就使哈希表对应位置-1。最后，遍历哈希表，若存在不等于0的元素则返回false。

【3】C++代码：

class Solution {
public:bool isAnagram(string s, string t) {int hash[26] = {0};for (int i = 0; i < s.length(); ++i) {++hash[s[i] - 'a'];}for (int i = 0; i < t.length(); ++i) {--hash[t[i] - 'a'];}for (int i = 0; i < 26; ++i) {cout << hash[i] << endl;if(hash[i] != 0)return false;}return true;}
};

【4】时间复杂度：O(N)，对于每个字符串只遍历了一次。

【5】空间复杂度：O(26)，开辟了额外存储26个字母个数的数组。

---

二、两个数组的交集（LeetCode--349）