【算法】代码随想录之哈希表（更新中）
文章目录
前言
一、有效的字母异位词（LeetCode--242）
二、两个数组的交集（LeetCode--349）
三、两数之和（LeetCode--1）
四、四数相加II（LeetCode--454）
五、三数之和（LeetCode--15）
六、四数之和（LeetCode--18）
前言
跟随代码随想录，学习哈希表相关的算法题目，记录学习过程中的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
【4】时间复杂度：O(N)，对于每个字符串只遍历了一次。
【5】空间复杂度：O(N)，开辟了额外的哈希表空间。
三、两数之和（LeetCode--1）
【1】题目描述：
【2】解决思想：哈希表法。遍历nums时查找哈希表中是否存在target-nums[i]的元素，若存在返回对应的下标，若不存在则将nums[i]插入哈希表中。
【3】C++代码：
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map hash;
for (int i = 0; i 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& nums1, vector& nums2, vector& nums3, vector& nums4) {
//遍历数组nums1和nums2，保存相加的值和出现次数
unordered_map 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) {
return ret;
}
//nums[i]去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
//双指针寻找符合条件的三元组
int left = i + 1, right = nums.size() - 1;
while (left 0) {//大于目标
right--;
} else {//小于目标
left++;
}
}
}
return ret;
}
};
【4】时间复杂度：O(N^2)，采用了双循环遍历。
【5】空间复杂度：O(1)。
