思路：

① 用一个长度为26的数组还记录magazine里字母出现的次数。

②用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

例题：力扣49

思路：

例题：力扣438

思路：

set作为哈希表

例题：力扣349 已完成

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

class Solution {
public:vector intersection(vector& nums1, vector& nums2) {/*set的写法unordered_set res_set;//存放结果,用set的目的是去重unordered_set nums_set(nums1.begin(),nums1.end());//存放num1的数据for(int num:nums2){//发现nums2的元素在nums_set中出现过if(nums_set.find(num)!=nums_set.end()){res_set.insert(num);//插入}}//返回结果return vector(res_set.begin(),res_set.end());*///数组的写法unordered_setres_set;//存放结果，用set对结果去重int hash[1005]={0};//默认值为0for(int num:nums1){ //nums1中出现的字母在hash中记录hash[num]=1;}for(int num:nums2){//nums2中出现的话，res记录if(hash[num]==1){res_set.insert(num);}}return vector(res_set.begin(),res_set.end());}
};

思路：unordered_set

①输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。

②如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

例题：力扣202 已完成

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

class Solution {
public://取数值各个位上的单数之和int getSum(int n){int sum=0;while(n){sum+=(n%10)*(n%10);n=n/10;}return sum;}bool isHappy(int n) {unordered_set resset;while(1){int sum=getSum(n);if(sum==1){return true;}//检测这个数之前是否出现过//如果这个数出现过，证明已经进入了循环，直接返回falseif(resset.find(sum)!=resset.end()){return false;}else{resset.insert(sum);//将sum数放进原来的集合里面，用下次判断}n=sum;//更新n的值}}
};

思路：

使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

例题：力扣350

思路：

map作为哈希表

例题：力扣1 已完成

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution {
public:vector twoSum(vector& nums, int target) {//1.map用来存放遍历过的元素，在遍历数组时询问集合中是否出现过这个元素//2.key用来存放元素，value用来存放下标std::unordered_mapmap;for(int i=0;isecond,i};}//如果没有找到匹配对，九八访问过的元素和下标存在map中map.insert(pair(nums[i],i));}return{};//如果没找到就返回空}
};

思路：

①map用来做什么：用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下表，这样才能找到与当前元素相匹配的

②map中的key和value分别表示什么：数组中的元素作为key，有key对应的就是value，value用来存下标

例题：力扣454 已完成

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

class Solution {
public:int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
unordered_map umap;key:a+b的数值，value:a+b数值出现的次数
for(int a:nums1){for(int b:nums2){umap[a+b]++;}
}
int count=0;//统计a+b+c+d=0出现的次数
//遍历C和D，找到如果如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来
for(int c:nums3){for(int d:nums4){if(umap.find(0-(c+d))!=umap.end()){count+=umap[0-(c+d)];}}
}
return count;}
};

思路：

①定义unordered_map，key放ab的和，value放ab和出现的次数

②遍历大A和B数组，统计两个数组元素之和，和出现的次数，放到map中

③定义遍历count，统计a+b+c+d=0出现的次数

④遍历CD数组，如果0-（c+d）在map中出现过，用count把map中key对应的value统计出来

⑤返回统计值count

双指针方法

用来解决三数、四数之和问题

例题：力扣15 已完成

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution {
public:vector> threeSum(vector& nums) {vector> result;sort(nums.begin(),nums.end()); //由于不返回数组下标 所以能进行排序 打乱顺序也不影响什么for(int i=0;i0){return result;}// 正确去重a方法if(i>0&&nums[i]==nums[i-1]){ //i>0保证数组不会越界continue;}int left=i+1;//left在当前头的右边第一个int right=nums.size()-1;//最后一个开始while(right>left){if(nums[i]+nums[left]+nums[right]>0){//值更大 缩小right=right-1;}else if(nums[i]+nums[left]+nums[right]<0){//值更小 扩大left=left+1;}else{result.push_back(vector{nums[i],nums[left],nums[right]});//储存满足条件的三元组while(right>left&&nums[right]==nums[right-1]) right--;//右边while(right>left&&nums[left]==nums[left+1]) left++;//左边//找到答案 双指针同时收缩left++;right--;}}}return result;}
};

思路：

①数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

②如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

③如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

④a的去重

⑤b、c的去重

例题：力扣18 已完成

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

class Solution {
public:vector> fourSum(vector& nums, int target) {vector> result;sort(nums.begin(),nums.end());//第一层循环for(int i=0;itarget&&nums[i]>=0){break;}//第一层去重if(i>0&&nums[i]==nums[i-1]){continue;}//第二层循环for(int j=i+1;jtarget&&nums[i]+nums[j]>=0){break;}//第二层去重if(j>i+1&&nums[j]==nums[j-1]){continue;}int left=j+1;int right=nums.size()-1;while(right>left){if((long long) nums[i] + nums[j] + nums[left] + nums[right] > target){right--;}else if((long long) nums[i] + nums[j] + nums[left] + nums[right] < target){left++;}else{result.push_back(vector{nums[i],nums[j],nums[left],nums[right]});// 对nums[left]和nums[right]去重while(left