哈希表
哈希表
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！
242. 有效的字母异位词
题目难度： 简单 用时： 5 分钟 标记： 完成
class Solution {
public:
//使用数组来进行哈希映射（因为只有26个字母，哈希表映射方便）
bool isAnagram(string s, string t) {
int arr[26] = {0};
for (int i = 0; i < s.size(); ++i) {
arr[s[i] - 'a']++;
}
for (int j = 0; j < t.size(); ++j) {
arr[t[j] - 'a']--;
}
for (int i = 0; i < 26; ++i) {
if (arr[i]!=0) return false;
}
return true;
}
};
49. 字母异位词分组
题目难度： 中等 用时： 30 分钟 标记： 完成
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string , vector<string>> umap; //定义一个map
for (auto newstr:strs) {
string ss = newstr;
std::sort(ss.begin(), ss.end());//对每个进行排序
umap[ss].push_back(newstr);//排序后加进去
}
vector<vector<string>> res;
for (auto newstr:umap) {
res.push_back(newstr.second);
}
return res;
}
};
438. 找到字符串中所有字母异位词
题目难度： 中等 用时： 25 分钟 标记： 完成
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(p.size() > s.size()) return {};
int map[26] = {0};
for (auto x :p) {
map[x - 'a']++;
}
vector<int> res;
for (int i = 0; i < s.size() - p.size() + 1; ++i) {
vector<int>new_map(begin(map),end(map));
for (int j = 0; j < p.size(); ++j) {
new_map[s[i + j] - 'a']--;
}
bool flag = false;
for (int k = 0; k < 26; ++k) {
if (new_map[k]!=0)
{
flag = true;
break;
}
}
if (!flag) res.push_back(i);
}
return res;
}
};
349. 两个数组的交集
题目难度： 简单 用时： 5 分钟 标记： 完成
class Solution {
public:
//unordered_set实现
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> uset(nums1.begin(),nums1.end());
vector<int> result;
unordered_set<int> unum2(nums2.begin(),nums2.end());
for (int i:unum2) {
if (uset.find(i)!=uset.end())
{
result.push_back(i);
}
}
return result;
}
};
350. 两个数组的交集 II
题目难度： 简单 用时： 6 分钟 标记： 完成
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
int map[1001] = {0};
int map2[1001] = {0};
for (auto x:nums1) {
map[x]++;
}
for (auto x:nums2) {
map2[x]++;
}
vector<int> res;
for (int i = 0; i < 1001; ++i) {
if (map[i]&&map2[i])
{
for (int j = 0; j < min(map[i],map2[i]); ++j) {
res.push_back(i);
}
}
}
return res;
}
};
202. 快乐数
题目难度： 简单 用时： 18 分钟 标记： 完成
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> umap;
while (umap.find(n)==umap.end()) //如果没有出现则加进去
{
umap.insert(n);
int sum = 0;//计算新的值
while (n)
{
sum+= (n % 10) *(n % 10) ;
n /= 10;
}
if (sum == 1) return true; //满足就返回
n = sum;
//cout << sum <<endl;
}
return false;
}
};
1. 两数之和
题目难度： 简单 用时： 6 分钟 标记： 完成
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>umap; //定义map
for (int i = 0; i < nums.size(); ++i) {
if (umap.find(nums[i])!=umap.end()) return {i,umap[nums[i]]};//查到map return
umap[target - nums[i]] = i;//没查到map 加入
}
return {};
}
};
454. 四数相加 II
题目难度： 中等 用时： 15 分钟 标记： 完成
//454. 四数相加 II
class Solution {
public:
/*
首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的 value也就是出现次数统计出来。
最后返回统计值 count 就可以了
注意：unordered_map初始值为0，可以直接加
用增强for循环（迭代器很好用）
*/
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> uAmap;
for (int i :nums1) {
for (int j:nums2) {
uAmap[i+j]++;
}
}
int sum = 0;
for (int i :nums3) {
for (int j:nums4) {
if (uAmap.find(-i-j)!=uAmap.end()) sum+=uAmap[-i-j];
}
}
return sum;
}
};
383. 赎金信
题目难度： 中等 用时： 3 分钟 标记： 完成
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int map[26]={0};//制作map
for (auto i :magazine) map[i - 'a']++;//遍历i++
for (auto i :ransomNote) map[i - 'a']--;
for (int i = 0; i < 26; ++i)
if (map[i] < 0) return false;
return true;
}
};
15. 三数之和
题目难度： 中等 用时： 30 分钟 标记： 未完成
//15. 三数之和
/*
****使用双指针法****
1.先对数组进行排序，循环变量i 为0 -> size-1
2.定义left = i+1 right = size-1指针
3.放left < right时指针收缩，找到满足条件则去重，并收缩
*/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> re;
int i ,left,right ;
for (i = 0; i < nums.size(); ++i) {
if (nums[i] > 0 ) return re; //第一个元素大于0则直接返回
if ( (i > 0) &&(nums[i] == nums[i-1])) continue; //i重复判断
left = i + 1;
right =nums.size()-1;
while (left < right)
{
if (nums[i] + nums[left] + nums[right] == 0) // 找到了
{
re.push_back(vector<int> {nums[i], nums[left], nums[right]}); //加入数组
while (left < right && nums[right]==nums[right-1]) right--; //右指针收缩
while (left < right && nums[left]==nums[left+1]) left++; //左指针收缩
//找到则两个指针收缩
left++;
right--;
continue;
}
if (nums[i] + nums[left] + nums[right] > 0)//没找到收缩
{
right--;
continue;
}
if (nums[i] + nums[left] + nums[right] < 0)//找到收缩
{
left++;
continue;
}
}
}
return re;
}
};
18. 四数之和
题目难度： 中等 用时： 30 分钟 标记： 未完成
//18. 四数之和
/*
与上题类似，多一层循环，多判断重复和减脂
*/
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int>> re;
int k,i ,left,right ;
for (k = 0; k < nums.size(); ++k) {
//一级剪枝
if (nums[k] > target && nums[k]>=0) break;
//一级去重
if ( k>0 && nums[k] == nums[k-1]) continue;
//二层循环 i
for (i = k+1; i < nums.size(); ++i) {
//二级剪枝
if ( (nums[k]+nums[i]) > target && (nums[k]+nums[i])>0) break;
//二级去重
if ( (i > k + 1) && nums[i] == nums[i-1]) continue;
left = i + 1;
right =nums.size()-1;
while (left < right)
{
if ((long)nums[k] + nums[i] +nums[left] + nums[right] == target) // 找到了
{
re.push_back(vector<int> {nums[k],nums[i], nums[left], nums[right]}); //加入数组
while (left < right && nums[right]==nums[right-1]) right--; //右指针收缩
while (left < right && nums[left]==nums[left+1]) left++; //左指针收缩
//找到则两个指针收缩
left++;
right--;
continue;
}
if ((long)nums[k] +nums[i] + nums[left] + nums[right] > target)//没找到收缩
{
right--;
continue;
}
if ((long)nums[k] +nums[i] + nums[left] + nums[right] < target)//找到收缩
{
left++;
continue;
}
}
}
}
return re;
}
};
205. 同构字符串
题目难度： 简单 用时： 10分钟 标记： 完成
class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s.size() != t.size()) return false;
unordered_map<char,char>umap;
for (int i = 0; i < s.size(); i++)
{
if (umap.find(t[i]) == umap.end()) umap[t[i]] = s[i];
else if(umap[t[i]] != s[i]) return false;
}
umap.clear();
for (int i = 0; i < s.size(); i++)
{
if (umap.find(s[i]) == umap.end()) umap[s[i]] = t[i];
else if(umap[s[i]] != t[i]) return false;
}
return true;
}
};
1002. 查找常用字符
题目难度： 简单 用时： 10分钟 标记： 完成
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<string> res;
int umap[26]={0};
for(int j = 0;j < words[0].size();j++) umap[words[0][j]-'a']++;
for(int i = 1; i < words.size();i++)
{
int cur[26] = {0};
for(int j = 0;j < words[i].size();j++) cur[words[i][j]-'a']++;
for(int j = 0;j < 26;j++) umap[j] = min(umap[j],cur[j]);
}
for(int i = 0; i < 26;i++)
{
while (umap[i] > 0)
{
string a(1,'a'+i);
res.push_back(a);
umap[i]--;
}
}
return res;
}
};
128. 最长连续序列
题目难度： 中等 用时： 8 分钟 标记： 完成
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> stes(nums.begin(),nums.end());
int maxs = 0;
int count = 1;
int pre = INT_MIN;
for (auto x:stes) {
if(pre == x - 1)count++;
else count = 1;
maxs = max(maxs,count);
pre = x;
}
return maxs;
}
};
149. 直线上最多的点数
暴力方法---先找到斜率，遍历相同的就加进来
题目难度： 困难 用时： 15分钟 标记： 完成
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
if (points.size() <= 2) return points.size();
int ans = 0;
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
int count = 2;
for (int k = j + 1; k < points.size(); k++) {
int x = points[k][0], y = points[k][1];
if ((y - y1) * (x2 - x1) == (y2 - y1) * (x - x1)) count++;
}
ans = max(ans, count);
}
}
return ans;
}
};
594. 最长和谐子序列
题目难度： 简单 用时： 10分钟 标记： 完成
class Solution {
public:
int findLHS(vector<int>& nums) {
map<int,int> uset;
for (int i = 0; i < nums.size(); ++i) uset[nums[i]]++;
if (uset.size() < 2) return 0;
int res = 0;
pair<int,int> pre(0,0);
for (auto x:uset) {
if (x.first - pre.first == 1 && pre.second!=0) res = max(res,x.second + pre.second);
pre = x;
}
return res;
}
};