242. 有效的字母异位词
解题思路：暴力解法就是两层for循环，另一种思路就是采用哈希表的方法。
首先定义一个可以刚好存放所有字母的数组，并且每个元素初始化为0。
接着首先对第一个字符串每个元素进行遍历，取出每个字符和a相减，相减可以得到当前字符在26个字母中所处的位置，然后将这个数字作为索引，让记录结果的数组result相应位置加上一。上述过程中，字母与result对应位置相互映射，形成了一个哈希表的结构。
接着遍历第二个字符串，同样通过和a的相减运算，得到了字符串中各个字符在result的位置映射，然后在相应位置做自减操作。
最终对结果数组进行遍历，查找是否有不等于0的位置，如果有，说明两字符串不满足要求，返回false。否则为真。
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
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) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
// record数组所有元素都为零0，说明字符串s和t是字母异位词
return true;
}
};
349. 两个数组的交集
解题思路：
这个题目也属于哈希表相关的题目，用到的数据结构叫做unordered_set，该容器的读取速率很高，而且不存在重复数据。当数组的元素数目很多的时候，使用数组会浪费较大的内存。
首先是用unordered_set的result_set来存放结果，再新建nums_set用于存放第一个数组。
接着遍历第二个数组中的每一个元素，通过find函数在nums_set中找该元素，找到的话，该函数会返回那个元素的迭代器，并将该元素放到结果数组中。如果不存在就会返回end()迭代器。
遍历完毕之后，由于结果都保存在了result中，返回值的类型要求是vector，所以将结果重新放到一个vector容器中。
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) {
// 发现nums2的元素 在nums_set里又出现过
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
当然本道题，如果对数组大小划定了范围，那么依然可以采用数组，完成哈希表的映射：把数组的数值映射到新的哈希数组的索引。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
int hash[1005] = {0}; // 默认数值为0
for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
hash[num] = 1;
}
for (int num : nums2) { // nums2中出现话，result记录
if (hash[num] == 1) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
202. 快乐数
解题思路：
当需要快速判断一个元素是否出现在一个集合中的时候，就可以考虑使用哈希法。
本题目的意思是，针对于一个整形数，每个数位上的数字求平方和，得到一个新的数字，然后继续同样的操作。
首先定义一个函数来完成对数字的每个位上的数字进行平方和操作。
然后，定义一个set集合，数据类型为unodered_set。接着定义一个死循环，不断进行求平方和操作，判断结果是否等一，结果是一的话，返回true。如果不为一，判断这个数之前是否出现过，如果出现过，说明陷入循环，但结果不为一，返回false。
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;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
1. 两数之和
解题思路：
由于改题目不仅需要确定是否存在，还要返回对应元素的索引，所以无法使用数组或集合，它们都只能映射为索引。但是map结构却可以映射为索引和值的组合。
首先遍历目标数组中的每个元素，然后找map中是否有有一个元素，它的值为目标值和当前元素的差值，也就是另一个目标元素的值。将返回值的迭代器返回给iter，用迭代器判断是否存在该目标值是否存在，如果存在，返回这个值的迭代器和当前元素的索引。如果返回的迭代器为end(),说明不存在，那么就将这个元素插入到map中。
如果直到遍历结束，都找不到这样的值，返回一个空vector。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
// 遍历当前元素，并在map中寻找是否有匹配的key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
