代码随想录算法训练营第五天|“巨燃”哈希表，本源双指针_code自留地的博客-爱代码爱编程
哈希表
哈希表总的来说有三种方式实现：
- 数组：适用于元素范围相对较小或者元素连续的情况
- 链表 + 哈希函数：我习惯的是拉链法，对于给定的值，我们的目的是将其存储到相对范围较小的hash槽中。对此我们可以设计出一个哈希函数，将给定的值映射到相应的hash中的位置，但是为什么称之为"链表 + 哈希函数"呢？那是因为我们在处理“哈希碰撞”的时候借鉴的其实是链表的思路，其实是用数组模拟的
- 直接用unordered_set或者unordered_map，存储单个的不重复的值就用set，需要存储键值对就用map
下面是拉链法的代码
拉链法代码
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 3; // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度
//* 开一个槽 h
int h[N], e[N], ne[N], idx; //h[]是哈希表上的所有位置，e[]用来存储值，ne[]用来记录相同h[]上的下一个元素的位置
//
void insert(int x) {
// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x) {
//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if (e[i] == x) {
return true;
}
}
return false;
}
int n;
int main() {
cin >> n;
memset(h, -1, sizeof h); //将槽先清空 空指针一般用 -1 来表示
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
insert(x);
} else {
if (find(x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
Leecode242.有效的字母异位词
链接：https://leetcode.cn/problems/valid-anagram/
class Solution {
public:
bool isAnagram(string s, string t) {
// 直接undered_map开淦！
unordered_map <char,int> hash;
int size_s = (int)s.size();
int size_t = (int)t.size();
for(int i=0;i<size_s;i++) {++hash[s[i]];}
for(int i=0;i<size_t;i++)
{
if(hash.find(t[i]) == hash.end()) return false;
auto it = hash.find(t[i]);
-- it->second;
if(it->second == 0) hash.erase(it);
}
if(hash.empty()) return true;
return false;
}
};
// 这道题可以用数组进行模拟
// 原因就是因为存储空间是连续的（字母的ASCLL码是连续的
Leecode349. 两个数组的交集
链接：https://leetcode.cn/problems/intersection-of-two-arrays/
还是水题。我的思路是先用set将一个数组遍历一遍，然后在遍历第二个数组的时候将其中的元素逐个取出并在set中find，若是find到了那么就在vector中加入这个元素并且在set中erase掉这个元素（因为输出元素是唯一的嘛）
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 用set也可以存啊
// 然后我们用迭代器遍历一遍？
unordered_set <int> hash;
vector<int> res;
// 其实讲的就是容器的用法嘛
// 直接遍历
int size1 = nums1.size();
int size2 = nums2.size();
for(int i=0;i<size1;i++) {hash.insert(nums1[i]);}
for(int i=0;i<size2;i++)
{
// 先取出元素
int num = nums2[i];
if(hash.find(num) != hash.end()) {res.push_back(num);hash.erase(num);}
}
return res;
}
};
Leecode202. 快乐数
链接：https://leetcode.cn/problems/happy-number/
虽然是简单题，但是一不小心就会不快乐喔~
首先介绍一下双指针的做法——其实不管在哪都能看到双指针的身影，这道题目也一样，但是为什么可以用双指针呢？因为题目需要判断有没有环
其实只要出现循环那就是环，这道题目某些测试点是会出现无限循环的，所以一定是需要判断有没有环的，忽然想起来在142题中我们用快慢指针解决过“判断环”的问题：用快慢指针，慢指针一次走一步，快指针一次走两步，这样若是有环就一定会相遇
// 现在用双指针的思路--判断有无环就用快慢指针！！！
// 慢指针做一次操作，快指针就做两次操作，如果两个指针值相等，就退出循环？这也太强了
// 若是有环自然可以输出，若是循环后值都是1，那么也可以输出，
// 所以最后判断值是不是1分别输出true或者false
class Solution {
public:
int cal(int x)
{
int sum = 0;
while(x)
{
sum += (x%10)*(x%10);
x/=10;
}
return sum;
}
bool isHappy(int n) {
int slow = n;
int fast = n;
while(1)
{
slow = cal(slow);
fast = cal(fast);
fast = cal(fast);
if(slow == fast) break;
}
return slow == 1;
}
};
然后我们看比较正常的用set的思路：
要想明白一个点：我们记录每次的快乐数，若是出现相同的快乐数，那么一定是出现了循环，因为每个快乐数的下一个快乐数都是固定的，那么若是出现了重复值，就一定出现了环
因此我们可以用set记录每次出现的快乐数，若是新出现的快乐数在set中存过了，那么一定有环，return false就可
同理若是出现了1我们直接return true
// 为什么这个题用集合做啊
// 因为循环的时候如果是出现了相同的元素，那么一定是陷入循环了，赶紧输出false
// 所以我们用set存储每次出现的元素，若是用set判断元素不等于hash.end()，那么说明一定是死循环了
// 除此之外还需要写一个计算每位平方和的函数
class Solution {
public:
unordered_set<int> hash;
int cal(int x)
{
int sum = 0;
while(x)
{
sum += (x%10) * (x%10);
x/=10;
}
return sum;
}
bool isHappy(int n) {
while(1)
{
int sum = cal(n);
// 首先应该判断是不是1吧，要是1的话直接就输出了呀
if(sum == 1) return true;
if(hash.find(sum)!= hash.end()) return false;
hash.insert(sum);
n = sum;
}
}
};
Leecode1.两数之和
链接：https://leetcode.cn/problems/two-sum/description/
签到题。用set记录每次出现的元素，并用for循环遍历数组中的元素，在我们已经知道了tar的条件下，直接用tar - arr[i]去搜set中有没有这个元素，有就返回下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 从头到尾遍历元素，遍历到一个元素就往set中加上一个元素
// 遍历到这个元素tar的时候，在set中搜索target - tar
// 若是找到了，直接返回下标，结束战斗
int size = nums.size();
unordered_map<int,int> hash; // 左边是值，右边是下标
for(int i=0;i<size;i++)
{
int cal = target - nums[i];
if(hash.find(cal)!= hash.end())
{
auto it = hash.find(cal);
return {i,it->second};
}
else hash.insert({nums[i],i});
}
return {};
}
};
Leecode454.四数相加
链接：https://leetcode.cn/problems/4sum-ii/
优化题。用四层for循环肯定会爆，所以我们要思考优化的方式
// 先想一下这个题的思路是什么？
// 因为四层for循环的时间复杂度太高了呀
// 所以比较优秀的做法就是把四层for循环拆成两个两个去做
// 这样n的四次方的时间复杂度就会降到n平方
// 刚开始的时候我们遍历前面两个数组，就是用两层for循环记录其中a+b出现的次数，所以我们使用的数据结构是unordered_map
// 之后我们遍历剩下的两个数组，判断 0-(c+d) 有无在记录的unordered_map中出现过，因为原本是(a+b+c+d)
// 所以若是满足条件，我们枚举的就是a+b的相反数
// 先判断0-(c+d)有无在hash中出现过，若是出现过，我们就用定义好的count变量加上出现过的次数
// 最后直接返回count就可以
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> hash;
for(auto i: nums1)
for(auto j: nums2)
++hash[i+j];
int count = 0;
for(auto k: nums3)
for(auto l: nums4)
{
int ans = -(k+l);
if(hash.find(ans) != hash.end()) count += hash[ans];
}
return count;
}
};
Leecode383.赎金信
链接：https://leetcode.cn/problems/ransom-note/
水题。先用map记录大串，然后遍历小串的时候用map减去小串中的元素，能减就合法，否则返回false
// map做法
// 其实就是观察magazine里面的字符能不能覆盖ransomNote
// 那么我们一开始应该怎么存？应该存较大的串，然后遍历较小的串，若是找不到元素，直接退出不就完了吗
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> hash;
int sizeA = ransomNote.size();
int sizeB = magazine.size();
for(int i=0;i<sizeB;i++) ++hash[magazine[i]];
for(int i=0;i<sizeA;i++)
{
if(hash.find(ransomNote[i])!=hash.end())
{
auto it = hash.find(ransomNote[i]);
-- it->second;
if(it->second == 0) hash.erase(it);
}
else return false;
}
return true;
}
};
// 数组做法
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int arr[26] = {0};
// 开始的时候先比较两个串的大小，要是左边的串大于右边的串，我们直接退出
if(ransomNote.size() > magazine.size()) return false;
for(int i=0;i<magazine.size();i++) ++arr[magazine[i] - 'a'];
for(int i=0;i<ransomNote.size();i++)
{
// 然后遍历较小的数组，若是索引处的值直接为0，就return false
if(arr[ransomNote[i] - 'a'] == 0) return false;
else --arr[ransomNote[i] - 'a'];
}
return true;
}
};
Leecode15.三数之和
链接：https://leetcode.cn/problems/3sum/
holyhigh的三数之和，需要注意的细节有点多
需要想明白为什么想到可以用双指针优化，又是为什么排序之后就可以用双指针优化
按理来说没有双指针的时候，在我们固定了left之后，剩余的两个数是要做两次for循环的，但是排序后用双指针就可以“有方向地”搜索，所以就将O(n^2)降到了(n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 回顾一下思路，是怎么做双指针的？是因为什么可以创造出使用双指针的条件的？
// 对数组进行排序之后，就可以得到双指针的使用条件——本来这道题目应该做三重for循环，双指针可以优化一层for循环，最后的时间复杂度是n平方
// 但是为什么排序之后就可以使用双指针了呢？双指针又为什么可以将原本的三层for循环变成两层呢？
// ————因为引入双指针后就不需要逐个元素遍历，题目条件是固定的，我们可以将其中的两层for循环的遍历“增加条件”，这样用一层for循环就搞定了，这就是双指针的本质
// 在对数组进行排序之后，由于目标固定，因此我们若是得到了大于或者小于目标值时，就可以通过双指针对二者之和进行调整，这也就是双指针的优化过程
// 我们首先写left处固定的元素，两层循环是避免不了的，此处不参与双指针的操作
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
int left = 0,right = nums.size() - 1;
for(;left<right - 1;left ++) // <right - 1,注意不可以写成<right，否则数组越界
{
if(left > 0 && nums[left] == nums[left-1]) continue;
// 细节，每次left的值改变以后，right都是从最右边开始
right = nums.size() - 1;
int mid = left + 1;
while(mid <= right-1)
{
// 然后对三者之和进行判断
// while(mid<right && nums[mid] == nums[mid+1]) mid++; // 若是把判断前后相等的循环条件放在前面，直接就跳过了000,参考用例[-5,-5,-4,-4,-4,-2,-2,-2,0,0,0,1,1,3,4,4]，当left = 0时，由于右侧right此时等于4，所以如果开始的时候就让mid一直往前走，肯定就会错过000的情况
// while(mid<right && nums[right] == nums[right-1]) right--;
int res = nums[left] + nums[mid] + nums[right];
if(res == 0)
{
ans.push_back({nums[left],nums[mid],nums[right]});
// 判断条件放置有问题，先写位置条件再写相等的条件，不然很容易就数据越界！坑死
// 一定不要把nums[mid] == nums[mid+1]写在while与循环的前面
while(mid<right-1 && nums[mid] == nums[mid+1]) mid++; // 这里写mid < right 也可以过，但不是合法的情况
while(mid<right-1 && nums[right] == nums[right-1]) right--;
mid++;
right--;
}
else if(res > 0) right --;
else if(res < 0) mid ++;
}
}
return ans;
}
};
Leecode18.四数之和
链接：https://leetcode.cn/problems/4sum/description/
怎么说，三数余孽（bushi）
不开long long见祖宗
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 还是用双指针来做
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int one = 0,four = nums.size()-1;
for(;one<=four - 3;one ++)
{
if(one > 0 && nums[one] == nums[one-1]) continue;
// 然后开始枚举第二个元素
for(int two = one+1;two<=four - 2;two++)
{
//注意第二个元素若是和之前值相等也就一直往前走啊
if(two > (one + 1) && nums[two] == nums[two-1]) continue;
// 然后就是喜闻乐见的双指针操作
int three = two + 1;
four = nums.size() - 1;
while(three <= four - 1)
{
long long ans = (long long)nums[one] + (long long)nums[two] + (long long)nums[three] + (long long)nums[four];
if((long long)target == ans)
{
// 把我们的答案直接加入到双层vector中
res.push_back({nums[one] , nums[two] , nums[three] , nums[four]});
while(three < four-1 && nums[three] == nums[three + 1]) three ++;
while(three < four-1 && nums[four] == nums[four - 1]) four --;
three ++;
four --;
}
else if (target > ans) three++;
else if (target < ans) four--;
}
}
}
return res;
}
};
淦！！