有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
由于题目中已经确定都是由小写字母组成的字符串，因此用一个大小为26的数组来表示哈希。
class Solution {
public:bool isAnagram(string s, string t) {int hash[26];int size_s=s.size(),size=t.size();if(size!=size_s)return false;for(int i=0;i<size_s;i++){hash[s[i]-'a']++;}for(int i=0;i<size;i++){hash[t[i]-'a']--;if(hash[t[i]-'a']<0)return false;}return true;}
};两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
本题需要熟悉unorderer_set的特性以及unordered_set和vector通过迭代器range初始化。
| 特性 | set | unordered_set |
|---|---|---|
| 序列 | 有序 | 无序 |
| 底层实现 | 红黑树（balanced binary search tree） | 哈希表（hash table） |
| 时间复杂度 | 插入、删除、查找操作 O(log n) | 插入、删除、查找操作 平均 O(1) |
| 迭代器 | 支持双向迭代器 | 仅支持前向迭代器 |
| 适用场景 | 需要排序存储、按序遍历场景 | 不需要排序、频繁查找和插入场景 |
// unordered_set的range构造
template <class InputIterator>unordered_set ( InputIterator first, InputIterator last,size_type n = /* see below */,const hasher& hf = hasher(),const key_equal& eql = key_equal(),const allocator_type& alloc = allocator_type() );// vector的range构造
template <class InputIterator>vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
set1首先将nums1的元素去重，set2将交集的结果去重。
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1(nums1.begin(),nums1.end());int sz2=nums2.size();unordered_set<int> set2;for(int i=0;i<sz2;i++){if(set1.find(nums2[i])!=set1.end()){set2.insert(nums2[i]);}}vector<int> res(set2.begin(),set2.end());return res;}
};快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
题目中快乐数的变化是无限循环的，因此用unordered_set或set来存储，如果变化过程中重复了，则返回false。
class Solution {
public:int changeNum(int n){int res=0;while(n){res+=(n%10)*(n%10);n/=10;}return res;}bool isHappy(int n) {unordered_set<int> hash;int tmp;while(1){tmp=changeNum(n);if(tmp==1)return true;if(hash.find(tmp)!=hash.end())return false;elsehash.insert(tmp);n=tmp;}}
};两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
题目要求找出两数相加之和为target的数组下标，因此我们用unorderred_map来存储已经遍历过的下标和数。首先查找target-nums[i]是否已经存在，若存在则返回答案。
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;int sz=nums.size();for(int i=0;i<sz;i++){auto tmp=hash.find(target-nums[i]);if(tmp!=hash.end()){return {i,tmp->second};}hash.insert({nums[i],i});}return {};}
};赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
ransomNote 和 magazine 由小写英文字母组成,看到这句话哈希就可以用一个26大小的数组。
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int sz1=ransomNote.size(),sz2=magazine.size();int hash[26];for(int i=0;i<sz2;i++){hash[magazine[i]-'a']++;}for(int i=0;i<sz1;i++){hash[ransomNote[i]-'a']--;if(hash[ransomNote[i]-'a']<0)return false;}return true;}
};四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出：2
本题要求元祖的个数，因此我们要用unordered_map来存储num1,num2的和和和的次数。之后遍历nums3和nums4，利用两数之和的思想。
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> hash;int sz1=nums1.size(),sz2=nums2.size(),sz3=nums3.size(),sz4=nums4.size();for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++){hash[nums1[i]+nums2[j]]++;}}int res=0;for(int i=0;i<sz3;i++){for(int j=0;j<sz4;j++){auto tmp=hash.find(0-nums3[i]-nums4[j]);if(tmp!=hash.end())res+=tmp->second;}}return res;}
};
