代码随想录算法训练营第六天 | 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数:和

242.有效的字母异位词

题目链接：242.有效的字母异位词

文章讲解：242.有效的字母异位词

视频讲解：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词_哔哩哔哩_bilibili

思路：

这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

判断一下字符串s= "aee", t = "eae"。

 定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做 1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

代码：

1.  
   class Solution {
2.  
   public:
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'] ;
8.  
   }
9.  
   for (int i = 0; i < t.size(); i ) {
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.  
    };

• 时间复杂度: O(n)
• 空间复杂度: O(1)

349. 两个数组的交集

题目链接：349. 两个数组的交集

文章讲解：349. 两个数组的交集

视频讲解：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集_哔哩哔哩_bilibili

思路：

要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

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

此时就要使用另一种结构体了，set ，关于set，C 给提供了如下三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

思路如图所示：

代码：

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4.  
   unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
5.  
   unordered_set<int> nums_set(nums1.begin(), nums1.end());
6.  
   for (int num : nums2) {
7.  
   // 发现nums2的元素 在nums_set里又出现过
8.  
   if (nums_set.find(num) != nums_set.end()) {
9.  
   result_set.insert(num);
10.  
    }
11.  
    }
12.  
    return vector<int>(result_set.begin(), result_set.end());
13.  
    }
14.  
    };

• 时间复杂度: O(mn)
• 空间复杂度: O(n)

思路：

这道题目中并不需要key有序，选择std::unordered_map 效率更高！

接下来需要明确两点：

• map用来做什么
• map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

过程如下：

 代码：

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> twoSum(vector<int>& nums, int target) {
4.  
   std::unordered_map <int,int> map;
5.  
   for(int i = 0; i < nums.size(); i ) {
6.  
   // 遍历当前元素，并在map中寻找是否有匹配的key
7.  
   auto iter = map.find(target - nums[i]);
8.  
   if(iter != map.end()) {
9.  
   return {iter->second, i};
10.  
    }
11.  
    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
12.  
    map.insert(pair<int, int>(nums[i], i));
13.  
    }
14.  
    return {};
15.  
    }
16.  
    };

• 时间复杂度: O(n)
• 空间复杂度: O(n)

这篇好文章是转载于：学新通技术网