算法题-哈希相关
哈希表
当采用哈希来解决问题的时候，一般会使用以下三种结构：
数组，集合（set），映射（map）
一文带你彻底读懂红黑树（附详细图解） - 知乎 (zhihu.com)
节点是红色或黑色
根是黑色
所有叶子都是黑色（叶子是NIL节点）
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）
一类需要用到unordered_map的题目
1. 两数之和 - 力扣（Leetcode）
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 *target* 的那 两个 整数，并返回它们的数组下标。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> umap;
for(int i=0;i<nums.size();i++){
if(umap.count(target-nums[i])>0) return vector<int>{i,umap[target-nums[i]]};
else umap[nums[i]]=i;
}
return {};
}
};
|
双指针——三数之和、四数之和
15. 三数之和 - 力扣（Leetcode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
if(nums[0]>0) return {};
for(int i=0;i<nums.size();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) right--;
else if(nums[i]+nums[left]+nums[right]<0) left++;
else{
res.emplace_back(vector<int>{nums[i],nums[left],nums[right]});
while(right>left&&nums[right-1]==nums[right]) right--;
while(right>left&&nums[left]==nums[left+1]) left++;
right--;
left++;
}
}
}
return res;
}
};
|
16. 最接近的三数之和 - 力扣（Leetcode）
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
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int left=0,right=nums.size()-1;
int leftmark=0,rightmark=0;
int res=INT_MAX;
int sumres=0;
for(int i=0;i<nums.size();i++){
if(i>0&&nums[i]==nums[i-1]) continue;
left=i+1;
right=nums.size()-1;
while(left<right){
int sum=nums[i]+nums[left]+nums[right];
if(sum>target) right--;
else if(sum<target) left++;
else return target;
int cur=abs(target-sum);
if(cur<res){
res=cur;
leftmark=left;
rightmark=right;
sumres=sum;
}
}
}
return sumres;
}
};
|
18. 四数之和 - 力扣（Leetcode）
注意如何避免重复！！！
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
| class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int left,right;
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();j++){
int left=j+1,right=nums.size()-1;
if(nums[i]+nums[j]>target&&nums[i]+nums[j]>=0) break;
if(j>i+1&&nums[j]==nums[j-1]) continue;
while(left<right){
long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
if(sum>target) right--;
else if(sum<target) left++;
else{
res.emplace_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
while(left<right&&nums[right]==nums[right-1]) right--;
while(left<right&&nums[left]==nums[left+1]) left++;
right--;
left++;
}
}
}
}
return res;
}
};
|