代码随想录 | Day08 | 哈希表：四数相加II&&赎金信&&三数之和&&四数之和
主要学习内容：
1.哈希表的使用
2.数量大于2的数组的话将两个数组加和转为一个数组进行哈希表的查找即可
3.双指针的用法
搞清楚双指针的定义和双指针移动条件
454.四数相加II
454. 四数相加 II - 力扣（LeetCode）
解法：哈希表
思路：
nums1中元素为a
nums2中元素为b
nums3中元素为c
nums4中元素为d
题目不要求去重则只需要统计a+b出现的次数
map的key为a+b，value为出现的次数
然后遍历3和4数组统计0-（c+d）在哈希表中出现的次数然后相加即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> p;
int res=0;
for(int a:nums1)
for(int b:nums2)
p[a+b]++;
for(int c:nums3)
for(int d:nums4)
if(p[-(c+d)]>0)
res+=p[-(c+d)];
return res;
}
};
|
关键点：要有用两个数之和表示两个数组的思路，这样就和两数之和一样了
383.赎金信
383. 赎金信 - 力扣（LeetCode）
解法：哈希表
数组来表示
在maganize中出现的字符就++
在ransomNote中出现的就–
如果小于0说明不够或者没有直接输出错误即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int hash[26]={0};
for(char c:magazine)
hash[c-'a']++;
for(char c:ransomNote)
{
hash[c-'a']--;
if(hash[c-'a']<0)
return false;
}
return true;
}
};
|
15.三数之和
15. 三数之和 - 力扣（LeetCode）
解法：双指针
思路：
如图所示我们选定的三个数由三个指针决定
分别是循环因子（a）以及快（c）慢（b）指针
1.快慢指针定义
慢指针从循环因子i的下一位置即i+1开始遍历
快指针从数组最后一个元素开始遍历
循环因子i，快慢指针就是我们要判断符不符合条件的三个数
2.快慢指针移动的条件
我们要用快慢指针必须要先对数组进行排序，让数组变得有序，这与循环条件和换慢指针的移动条件有关
排序过后
如果三数之和nums[i]+nums[l]+nums[r]小于0，则说明慢指针l小了一点，就需要后移
如果三数之和nums[i]+nums[l]+nums[r]大于0，则说明快指针l大了一点，就需要前移
如果等于0那么就是答案，快慢指针同时收缩，快指针后移，慢指针前移
3.关于三个元素的去重问题
对于循环因子i所指向的元素（a），我们只需当i和i-1元素一样时那么就跳过当前元素就相当于去重，集合中就不会有a的重复
关于快慢指针则需要单独处理
并且只需要在找到答案时单独处理，没有找到答案时只是指针移动不需要去重
找到答案后，很有可能l=l+1的元素或者r=r-1的元素，这样就会造成重复的答案
然而并一定只有一位相同因此我们需要用whie，直到快慢指针的下一元素和当前元素不同
另外关于a，b，c的去重在写的时候有可能碰到的问题
1.i和i-1比较而不是i和i+1
2.b，c去重要在找到答案后而不是while一开始就去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int length=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>0)
continue;
if(i>0&&nums[i-1]==nums[i])
continue;
int l=i+1;
int r=nums.size()-1;
while(l<r)
{
if(nums[i]+nums[l]+nums[r]>0)
r--;
else if(nums[i]+nums[l]+nums[r]<0)
l++;
else
{
res.push_back(vector<int>({nums[i],nums[l],nums[r]}));
while(r>l&&nums[r-1]==nums[r]) r--;
while(r>l&&nums[l+1]==nums[l]) l++;
l++;
r--;
}
}
}
return res;
}
};
|
关键点：
1.对数组进行排序
2.循环条件
3.对三个元素的去重操作
解法：哈希表
这个思路简单和四数相加差不多，都是两个数组和表示一个元素然后在哈希表中找剩下一个元素，但是去重非常麻烦在这里就不过多赘述（我觉得掌握双指针够用了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int l = i + 1;
int r = nums.size() - 1;
while (r > l) {
if (nums[i] + nums[l] + nums[r] > 0) r--;
else if (nums[i] + nums[l] + nums[r] < 0) l++;
else {
result.push_back(vector<int>{nums[i], nums[l], nums[r]});
while (r > l && nums[r] == nums[r - 1]) r--;
while (r > l && nums[l] == nums[l + 1]) l++;
r--;
l++;
}
}
}
return result;
}
};
|
18.四数之和
18. 四数之和 - 力扣（LeetCode）
解法：双指针
思路：
所以最好先做三数之和
总体思路就是在三数之和上面多加了一套while循环而已
我们选定的四个数由四个指针决定
分别是循环因子i,j（a,b）以及快（d）慢（c）指针
1.快慢指针定义
j从i的下一位置开始遍历
慢指针从循环因子j的下一位置即j+1开始遍历
快指针从数组最后一个元素开始遍历
循环因子i，快慢指针就是我们要判断符不符合条件的三个数
2.快慢指针移动的条件
我们要用快慢指针必须要先对数组进行排序，让数组变得有序，这与循环条件和换慢指针的移动条件有关
排序过后
如果三数之和nums[i]+nums[l]+nums[r]小于target，则说明慢指针l小了一点，就需要后移
如果三数之和nums[i]+nums[l]+nums[r]大于target，则说明快指针l大了一点，就需要前移
如果等于0那么就是答案，快慢指针同时收缩，快指针后移，慢指针前移
3.关于四个元素的去重问题
对于循环因子i所指向的元素（a），我们只需当i和i-1元素一样时那么就跳过当前元素就相当于去重，集合中就不会有a的重复
对于循环因子j所指向的元素（b），除了和a一样的操作以外，这里包含了一种特殊情况当j-i=1，即i，j相邻时，两个数一样，这时不能continue因为会跳过一种情况，那么就必须要加上j-i大于1这一项
关于快慢指针则需要单独处理
并且只需要在找到答案时单独处理，没有找到答案时只是指针移动不需要去重
找到答案后，很有可能l=l+1的元素或者r=r-1的元素，这样就会造成重复的答案
然而并一定只有一位相同因此我们需要用whie，直到快慢指针的下一元素和当前元素不同
另外关于a，b，c,d的去重在写的时候有可能碰到的问题（）具体请看三数之和
1.i和i-1比较而不是i和i+1
2.b，c去重要在找到答案后而不是while一开始就去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i=0;i<nums.size();i++)
{
if(nums[i]>target&&nums[i]>=0)
break;
if(i>0&&nums[i]==nums[i-1])
continue;
for(int j=i+1;j<nums.size()-1;j++)
{
if (nums[j] + nums[i] > target && nums[j] + nums[i] >= 0) {
break;
}
if((j-i>1)&&nums[j]==nums[j-1])
continue;
int l=j+1;
int r=nums.size()-1;
while(l<r)
{
if((long long)nums[i] + nums[l] + nums[r] + nums[j] > target)
r--;
else if((long long)nums[i] + nums[l] + nums[r] + nums[j] < target)
l++;
else
{
res.push_back({nums[i],nums[l],nums[r],nums[j]});
while(l<r&&nums[r]==nums[r-1]) r--;
while(l<r&&nums[l]==nums[l+1]) l++;
l++;
r--;
}
}
}
}
return res;
}
};
|
哈希表章节总结
1.数组，set，map一共三种哈希表
各有各的使用场景
2.set的操作如find，count等熟练
3.双指针yyds
微信
支付宝
