1.有效异位词
242. 有效的字母异位词
直接使用库函数的multiset来判断
其实没什么好说的，因为字符串有重复的可以出现所以用的multiset
缺点：确实浪费空间，红黑树的插入删除，浪费时间
class Solution {
public:bool isAnagram(string s, string t) {multiset<char> ms;multiset<char> mt;for (auto e : s)ms.insert(e);for (auto e : t)mt.insert(e);if (ms.size() != mt.size())return false;auto begin1 = ms.begin();auto begin2 = mt.begin();while (begin1 != ms.end()){if (*begin1 != *begin2)return false;begin1++;begin2++;}return true;}
};2.数组实现
26个小写字母，而且是连续的，那么我们直接用数组来存储也可以的
1.那么映射的方式也很简单了，a就对应下标0，z对应下标25
2.第一个string里的字符对应下标元素有则加一；第二个是减一
3.到这里说明两个string都应该映射过了，那么我们检查hash是不是已经全为空，如果不是失败；反之成功
class Solution {
public:bool isAnagram(string s, string t) {int hash[26]={0};for(auto e:s)hash[e-'a']++;for(auto e:t)hash[e-'a']--;for(int i=0;i<26;i++){if(hash[i]!=0)return false;}return true;}
};2.数组交集
349. 两个数组的交集
用unordered_set去重，用unordered_map计数
1.unordered_set插入所有元素，不重复出现
2.unordered_map把两个unordered_set中的东西判断一下，遍历如果是1的就是交集
缺点：简单问题复杂化了
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;unordered_set<int> s1;unordered_set<int> s2;unordered_map<int,int> m;for(auto& e:nums1)s1.insert(e);for(auto& e:nums2)s2.insert(e); for(auto& e:s1)m[e]++;for(auto& e:s2)m[e]++; for(auto& e:m){if(e.second==2)ret.push_back(e.first);}return ret;}
};优化过的
1.ret_set用来存储两个的交集
2.num_set存储nums1的所有元素
3.遍历一遍nums2，在num_set中能找到的说明是交集要插入ret_set，ret_set能去重
4.返回ret_set里的元素就行了
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> ret_set;unordered_set<int> num_set(nums1.begin(),nums1.end());for(auto e:nums2){if(num_set.find(e)!=num_set.end())ret_set.insert(e);}vector<int> ret(ret_set.begin(),ret_set.end());return ret;}
};数组实现
由于其数据个数范围在1~1000，因此我们通过数组实现也可以
unordered_set的缺点是哈希冲突会调用内部函数调整，这也减少了效率
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> ret_set;int hash[1001]={0};for(auto e:nums1)hash[e]=1;for(auto e:nums2){if(hash[e]==1)ret_set.insert(e);}vector<int> ret(ret_set.begin(),ret_set.end());return ret;}
};3.快乐数
202. 快乐数
一个数拆开平方相加其实很好写，重要的是怎么判断重复了。因此哈希表是一个很好的查重
1.先定义一个unordered_set，并且插入n
2.n没到1或者没有重复都要不停循环，那么我们结束循环条件就是n为1
3.定义一个临时遍历sum，它用来算n拆开后的平方的总和，再把n变成sum
4.这下就要看n有没有重复，重复则返回false；没有则依然循环
5.结束循环说明n为1，那么就返回true
class Solution {
public:bool isHappy(int n) {unordered_set<int> us;us.insert(n);while(n!=1){int sum = 0;while(n){sum+=(n%10)*(n%10);n/=10;}n=sum;if(us.find(n)==us.end())us.insert(n);elsereturn false;}return true;}
};4.两数之和
1. 两数之和
暴力求法
两层循环就行了
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){if(nums[i]+nums[j]==target)return {i,j};}}return {};}
};洋洋洒洒写完后，看就这么几个字
"你可以想出一个时间复杂度小于
O(n^2)的算法吗？" -- 要求反而是一种提示。哈希表
1.回顾一下我们要干什么，我们要上两个数加起来等于目标的
2.那么我们如果已经知道一堆数加起来一定不能等于目标，下一个加进来的，能不能利用已知前面的特性去专门找有没有符合的呢？两层暴力循环意味着我们没有利用起来已经遍历过的数，所以哥们觉得这也可以优化
3.遍历一个数，我们先将target减去这个数，看看表里有没有，没有就插入这个表；有的话就结束了。优化到时间复杂度为O(N)啊！
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> um;int num = 0;for(auto e:nums){if(um.find(target-e)==um.end())um.insert(make_pair(e,num++));elsereturn {um.find(target-e)->second,num++};}return {};}
};
