242.有效的字母异位词
卡哥建议： 这道题目，大家可以感受到数组用来做哈希表给我们带来的遍历之处。题目链接/文章讲解/视频讲解：
https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
做题思路：
常见的三种哈希结构有如下三种数据结构。数组，set （集合）map(映射)
字母异位词（观察出的）就是看两个字符串里的所有字母是否都相同，且出现的次数是否也都相同。观察测试用例的两个字符串，会发现除了位置上的字母不同外，还有字母的次数是都相同的，所以从次数入手，可以用哈希表记录下第一个字符串的各字母出现的次数，再用第二个字符串的各字母出现的次数在哈希表中减减，最后看是否为0，为0就说明相同。
本题代码：
1 #include <iostream>
2 using namespace std;
3 bool isAnagram(string s, string t) {
4 int record[26] = { 0 }; //数组初始化
5 for (int i = 0; i < s.size(); i++) { //统计第一个字符串各字母的次数
6 // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
7 record[s[i] - 'a']++; //比如字符串s[0]='a',那'a'-'a'=0,record[0]++，遇到其他字母，次数也就保存在对应的26个字母表位置上
8 }
9 for (int i = 0; i < t.size(); i++) { //让第二个字符串的各字母的次数在record数组上减减
10 record[t[i] - 'a']--;
11 }
12 for (int i = 0; i < 26; i++) {
13 if (record[i] != 0) {
14 // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
15 return false;
16 }
17 }
18 // record数组所有元素都为零0，说明字符串s和t是字母异位词
19 return true;
20 }
21 int main()
22 {
23 string s;
24 cin >> s; //输入字符串的时候，一定不能输空格，连续输入字符就行
25 string t;
26 cin >> t;
27 if(isAnagram(s,t))
28 {
29 cout << "true" << endl;
30 }
31 else
32 {
33 cout << "false" << endl;
34 }
35 return 0;
36 }
运行结果：
349. 两个数组的交集
卡哥建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html
做题思路：
1，以属于A且属于B的元素为元素的集合称为A与B的交集，如果给的两个数组，有两个相同的数都属于两个数组，那只取一个数就行，所以去重正好是set集合的一个特点，（如果这道题目没有限制数值的大小，就无法使用数组来做哈希表了，因为哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set）。我们可以把第一个数组放进哈希表中，再遍历第二个数组的元素，看哈希表是否出现过相同的元素，把相同的元素放进结果集合中。
2，set的 find 函数返回一个指向被查找到元素的迭代器，如果没找到，返回的是 set.end()。
3，见卡哥文章的后记，用数组的话，直接把部分代码一改，再放到下面的代码里运行。
本题代码：
1 #include <iostream>
2 #include <unordered_set>
3 #include <vector>
4 using namespace std;
5 vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
6 {
7 unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
8 unordered_set<int> nums_set(nums1.begin(), nums1.end());
9 for(int num : nums2) //num是遍历第二个数组的迭代器，用的是增强for循环遍历，不能用set集合遍历方式
10 {
11 // 发现nums2的元素 在nums_set里又出现过
12 if (nums_set.find(num) != nums_set.end()) //不等于哈希表的末尾，那就说明哈希表末尾之前出现过了第二个数组中的元素
13 {
14 result_set.insert(num);
15 }
16 }
17 return vector<int>(result_set.begin(), result_set.end());
18 }
19 int main()
20 {
21 vector<int> nums1;//第一个数组，第二个数组用vector容器存放
22 vector<int> nums2;
23 int n1;
24 cin >> n1;
25 for(int i = 0; i < n1; i++)
26 {
27 int num1 = 0;
28 cin >> num1;
29 nums1.push_back(num1); //把第一个数组添加到容器中
30 }
31 int n2;
32 cin >> n2;
33 for(int i = 0; i < n2; i++)
34 {
35 int num2 = 0;
36 cin >> num2;
37 nums2.push_back(num2);
38 }
39 vector<int> res = intersection(nums1,nums2); //将结果接收
40 for(vector<int>::iterator it = res.begin(); it != res.end(); it++) //vector容器的遍历
41 {
42 cout << (*it) << " ";
43 }
44 cout << endl;
45 return 0;
46 }
运行结果：
1. 两数之和
卡哥建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
做题思路：什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
1，给了一个数组和目标值，通过遍历数组的元素，用目标值对当前遍历的元素减，看相差的数是多少，如果相差的数正好和我们前某个遍历的元素一样(遍历过的元素都放在集合里，所以要想到哈希法），那就返回前一个遍历的元素的下标和当前遍历的元素下标，比如，目标值是9，当前是7，那看9-7=2是否遍历过就行。
2，用map的原因：因为我们是要查找元素在集合里有没有出现过或者遍历过，再返回元素对应的下标，而在map里通过key索引，得到了value，所以这个题的元素对应着key，下标对应着value，用map合适。
3，C++中map，有三种类型：map，multimap，unordered_map，map 和 multimap 的key也是有序的，这道题目中并不需要key有序，选择std::unordered_map 效率更高！
本题代码：
1 #include <iostream>
2 #include <unordered_map>
3 #include <vector>
4 using namespace std;
5 vector<int> twoSum(vector<int>& nums, int target)
6 {
7 unordered_map<int,int> map; //存放遍历过的元素的哈希表
8 for(int i = 0; i < nums.size(); i++)
9 {
10 // 遍历当前元素，并在map中寻找是否有匹配的key
11 auto iter = map.find(target - nums[i]); //auto 自动推断变量的类型
12 if(iter != map.end())
13 {
14 return {iter->second, i};//和原本的map反过来了，原本的是通过索引找到值，现在通过值(元素)找索引(下标)
15 }
16 // 如果没找到匹配对，就把访问过的元素和下标加入到map中
17 map.insert(pair<int, int>(nums[i], i)); //map所有元素都是pair对组，没找到的话，就把遍历过的元素和下标放到 map里
18 }
19 return {};
20 }
21 int main()
22 {
23 vector<int> nums;
24 int n;
25 cin >> n;
26 for(int i = 0; i < n; i++)
27 {
28 int num = 0;
29 cin >> num;
30 nums.push_back(num);
31 }
32 int target;
33 cin >> target;
34 vector<int> res = twoSum(nums,target); //将结果接收
35 for(vector<int>::iterator it = res.begin(); it != res.end(); it++) //vector容器的遍历
36 {
37 cout << (*it) << " ";
38 }
39 cout << endl;
40 return 0;
41 }
运行结果：
标签：vector,map,set,int,随想录,遍历,数组,349,两数 From： https://www.cnblogs.com/romantichuaner/p/17593178.html