当前位置：首页 > news >正文

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

news 2025/2/23 1:05:13

242.有效的字母异位词

题目链接：242.有效的字母异位词
文档讲解：代码随想录有效的字母异位词
视频讲解：LeetCode：有效的字母异位词
状态：学会了

思路：
数组其实是简单哈希表。
哈希表用来快速判断元素是否在一个集合里面出现。
哈希表（数组）：需要把字符映射到数组也就是哈希表的索引下标，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射下标0，相应字符z映射为下标25。哈希表设计为长为26的数组。哈希函数为s[i] - ‘a’，映射为字符的ASCII值。最后record数组有元素不为零，说明字符串s和t一定是字符数不同，return false。否则遍历后，return true。

时间复杂度：O(n)
空间复杂度：O(1)，record是定义的一个常量大小的辅助数组。

// 哈希表：数组就行
class Solution {
public:bool isAnagram(string s, string t) {// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了int record[26] = {0};// 记录s字母情况for (int i = 0; i < s.size(); i++) {record[s[i] - 'a']++;}// 记录t字母情况for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}// 判断是否数组元素都为0// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。for (int i = 0; i < 26; i++) {if (record[i] != 0) return false;}// record数组所有元素都为零0，说明字符串s和t是字母异位词return true;}
};

349. 两个数组的交集

题目链接：349. 两个数组的交集
文档讲解：代码随想录两个数组的交集
视频讲解：LeetCode：两个数组的交集
状态：

思路：
这道题不能用数组来做，原因是使用数组来做哈希的题目，是因为题目都限制了数值的大小，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。但是这道题没有，所以考虑哈希表另一种常见类型。
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

哈希表（unordered_set）：设计一个ordered_map来存储交集元素，返回是一个数组。去重记录，比较，然后存储，最后转换。思路如下：
在这里插入图片描述

时间复杂度：O(n+m)，m是因为最后set转换为vector
空间复杂度：O(n)

// 哈希表：unordered_set
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 哈希表 ：unordered_set：去重、无序、快unordered_set<int> result_set;// 去重nums1unordered_set<int> nums1set(nums1.begin(), nums1.end());// 在nums2中查找for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums1set.find(num) != nums1set.end()) {result_set.insert(num);}}// 返回数组形式return vector<int>(result_set.begin(), result_set.end());}
};