温习数据结构与算法，准备一些比赛，为了学业和就业，以及提升自己的编程能力，将系统的刷刷算法，入手c++跟着carl，leetcode刷题笔记将持续更新…
哈希表是根据关键码（索引下标）的值而直接进行访问的数据结构。
一般哈希表都是用来快速判断一个元素是否出现集合里。牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
冲突解决：拉链法，线性探测法
使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构：
242.有效的字母异位词
力扣题目链接
【法一】直接用sort函数，字母排序比较
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(),s.end());
sort(t.begin(),t.end());
if(s==t)
return true;
else
return false;
}
};
【法二】map计数 原理也是哈希计数（字母，出现次数）
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char,int> map;
if (s.size() != t.size())
return false;
for(int i=0;i<s.size();i++){
++map[s[i]];
--map[t[i]];
}
for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
if(it->second!=0)
return false;
}
return true;
}
};
【法三】哈希计数效率最高（字母对应数组下标，数组存储出现次数）
因为哈希表的计数排序时间复杂度为O(L+n)，其中L是哈希表长，n是数据规模，而常用的排序算法为O(nlogn)。当数据规模n很大的时候，计数排序的性能就体现出来。
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
return false;
}
}
return true;
}
};
349. 两个数组的交集
力扣题目链接
注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序
但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：
- std::set
- std::multiset
- std::unordered_set
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
for (int i = 0; i < nums2.size();i++) {
int num = nums2[i];
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
find() ，返回给定值值得定位器，如果没找到则返回end()。
insert(key_value); 将key_value插入到set中 ，返回值是****pair<set::iterator,bool>****，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。
202. 快乐数
力扣题目链接
set.find(sum) != set.end()判断sum是否重复出现,使用unordered_set
找到返回值下标，没找到返回end
class Solution {
public:
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
两数之和
力扣题目链接
两数之和，无序常用unordered_map哈希表存储，map(值，下标)，map中存的也是一个个pair
找到互补元素，pair对组形式返回 {iter->second, i} {找到的互补元素下标，准备存的元素下标}
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
454.四数相加II
力扣题目链接
四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，只统计次数，不用返回元组，不需去重
分组 + 哈希表
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap;
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0;
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
15. 三数之和
力扣题目链接
排序 + 双指针
本题的难点在于如何去除重复解。
-
可以加一个特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 [][]。 if (nums.size() < 3) return result; -
对数组进行排序。 -
遍历排序后数组：
-
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。 -
对于重复元素：跳过，避免出现重复解 -
令左指针 L=i+1，右指针 R=n-1，当 L<RL<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,R 移到下一位置，寻找新的解 若和大于 0，说明 nums[R] 太大，RR 左移
若和小于 0，说明 nums[L] 太小，LL 右移
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 left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
};
18. 四数之和
力扣题目链接
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针
类比三数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
right--;
} else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}
};
|