文章目录
前言
跟随代码随想录,学习哈希表相关的算法题目,记录学习过程中的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)。