【算法】代码随想录之哈希表（更新中）
文章目录
前言
跟随代码随想录，学习哈希表相关的算法题目，记录学习过程中的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）
【1】题目描述：
【2】解决思想：哈希表法。首先，遍历nums1数组，将所有元素作为first添加到哈希表中，其second为0（若元素重复则不添加）。其次，遍历nums2数组，查找哈希表中是否存在元素，若存在且没有重复添加到ret则添加到目标数组ret中，每次添加完毕后令其值为1（用来标识是否已经添加过）。最后，返回目标数组ret。
【3】C++代码：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hash;
vector<int> ret;
//遍历nums1，将元素添加到哈希表中，值为0
for (int i = 0; i < nums1.size(); ++i) {
auto p = hash.find(nums1[i]);
if (p == hash.end()) {
hash.insert(make_pair(nums1[i], 0));
}
}
//遍历nums2，若哈希表中存在且不重复则添加到ret中
for(int i = 0; i < nums2.size(); ++i) {
auto p = hash.find(nums2[i]);
if (p != hash.end() && p->second == 0) {
p->second = 1;
ret.push_back(nums2[i]);
}
}
return ret;
}
};【4】时间复杂度：O(N)，对于每个字符串只遍历了一次。
【5】空间复杂度：O(N)，开辟了额外的哈希表空间。
三、两数之和（LeetCode--1）
【1】题目描述：
【2】解决思想：哈希表法。遍历nums时查找哈希表中是否存在target-nums[i]的元素，若存在返回对应的下标，若不存在则将nums[i]插入哈希表中。
【3】C++代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); ++i) {
auto p = hash.find(target - nums[i]);
if (p != hash.end()) {
return {p->second, i};
}
hash.insert(make_pair(nums[i], i));
}
return {};
}
};【4】时间复杂度：O(N)，只遍历了一次nums数组。
【5】空间复杂度：O(N)，开辟了额外的哈希表空间。
四、四数相加II（LeetCode--454）
【1】题目描述：
【2】解决思想：哈希表法。首先，双循环遍历nums1和nums2，将它们相加的值保存到哈希表的first中且second为1，若它们已经存在于哈希表中则将second++。其次，双循环遍历nums3和nums4，在哈希表中寻找0-(nums3[i]+nums4[j])，若找到则将ret++。最后，返回ret。
【3】C++代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
//遍历数组nums1和nums2，保存相加的值和出现次数
unordered_map<int, int> hash;
for (int a : nums1) {
for (int b : nums2) {
hash[a + b]++;
}
}
//遍历数组nums3和nums4，查找0-相加的值是否存在于哈希表中
int ret = 0;
for (int c : nums3) {
for (int d : nums4) {
if (hash.find(0 - c - d) != hash.end()) {
ret += hash[0 - c - d];
}
}
}
return ret;
}
};【4】时间复杂度：O(N^2)，采用了双循环遍历。
【5】空间复杂度：O(N^2)，开辟了额外的哈希表空间。
五、三数之和（LeetCode--15）
【1】题目描述：
【2】解决思想：双指针法，而不用哈希表法（哈希表法去重较为麻烦）。首先，对nums进行从小到大的排序，那么当nums[i]大于0时后续就不可能有符合要求的三元组。其次，left指针指向i+1，right指针指向最后一个元素，在i固定时循环判定i、left、right这三个位置的元素之和是否等于0，若为0则添加到结果数组中，若>0说明太大让right--，若<0说明太小让left++。注意：i、left和right这三个位置都要做去重处理。
【3】C++代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
//从小到大排序
sort(nums.begin(), nums.end());
//双指针法
for (int i = 0; i < nums.size(); ++i) {
//某个元素已经大于0，后续部分中不可能有负数
if (nums[i] > 0) {
return ret;
}
//nums[i]去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
//双指针寻找符合条件的三元组
int left = i + 1, right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {//符合
ret.push_back(vector<int>{nums[i], nums[left], nums[right]});
//找到三元组后对第二、三个元素去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
left++;
} else if (nums[i] + nums[left] + nums[right] > 0) {//大于目标
right--;
} else {//小于目标
left++;
}
}
}
return ret;
}
};【4】时间复杂度：O(N^2)，采用了双循环遍历。
【5】空间复杂度：O(1)。
六、四数之和（LeetCode--18）
原文地址：https://blog.csdn.net/weixin_46249470/article/details/140477857
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！