代码随想录打卡 Day 3

1. 哈希表的理论基础

哈希表的定义

哈希表是根据关键码的值直接访问数据的数据结构，一般用来快速判断一个元素出现在集合中。

数组就可以看成是一张哈希表，这张哈希表中的关键字 就是数组的索引下标，值就是数组中的元素。

哈希表的基本概念

哈希表的基本概念包括:

• 哈希函数:对于关键字$k$,通过哈希函数将其储存到$f(k)$的位置，因此，不需要通过比较就可以获取所查的记录。
• 哈希碰撞:对于不同的关键字，可能得到同一个散列地址，这一现象为哈希碰撞。一般来说，哈希碰撞的解决方法有拉链法和线性探测法，在此不再赘述。

哈希表的常见结构:

使用哈希表解决问题时，常见的数据结构有:数组，set(集合),map(映射)。

在CPP中，set在STL中共有三种实现方式,如下表所示:

map的底层实现同样包括三种:

使用哈希法时，不同的数据结构一般有不同的使用场景，如下所示:

2.有效的字母异位词

leetcode题号:242.有效的字母异位词

【题目描述】

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

【题目分析】

在本题中，我们可以定义一个长度为26的数组record初始化为0。这是因为字符a到z的ASCII值为26个连续数值。

在遍历字符串s时，只需要对s[i]-'a'所在元素+1即可，并不需要记住ASCII码，只需要求出一个相对数值即可。

检查字符串t是否出现了这些字符？在遍历字符串t的过程中，对t出现的字符映射到索引上的值-1即可。

如果record数组中的元素不全为0，则说明s与t不是有效的字符异位词，返回false。

本题的相关代码如下:

bool isAnagram(string s, string t) {
    int record[26]={0};//新建一个数组，用来记录每个字母出现的次数
    for(int i=0;i<s.size();i++){ //对string s 遍历
        record[s[i]-'a']++;  //s[i]-'a'是计算s[i]在字母表中的位置，然后record[s[i]-'a']++，即记录每个字母出现的次数
    }


    for(int i=0;i<t.size();i++){ //对string t 遍历
        record[t[i]-'a']--;
    }

    for (int i=0;i<26;i++){
        if(record[i]!=0){
            return false;
        }
    }

    return true;//record所有数组元素均为0
}

相比于暴力解法，该解的时间复杂度为$O(n)$，空间复杂度为$O(n)$.

3. 两个数组的交集

leetcode题号:349.两个数组的交集

【题目描述】

计算两个数组的交集，交集中的元素是唯一的。

【题目分析】

解答本题，主要是学习哈希数据结构—unordered_set.

题目中睡哦名，输出的每一个元素一定是唯一的，同时不需要考虑输出结果的顺序。

如上一题所讲，将数组当作哈希表页数不错的选择，但本题中，数组元素内容并没有限制。如果哈希值较少，比较分散，跨度大，使用数组作为哈希表数据结构就会造成很大的内存空间浪费。此时，就应该适用set这种数据结构。

第一部分的表格已经指出了三种set数据结构的差异。其中std::unordered_set的底层实现是哈希表，不同于其他两种结构依赖红黑树。适用unordered_set的I/O效率是最高的，不需要对数据进行排序的同时保证了数据的唯一性。

unordered_set的基本操作

unordered_set的基本操作如下:

# 构造函数
std::unordered_set<int> uset;

# 插入元素
uset.insert(10);

# 查找元素
auto it = uset.find(10);
#如果查找失败，it == uset.end();

# 遍历元素
for(auto it = uset.begin(),it != uset.end(); it++){
    \*  for loop *\
}
# 其中begin()方法提供一个正向迭代器，end()方法提供一个福祥迭代器

# 删除元素
uset.erase(10);

# 大小与空检查
size_t size = uset.size();
bool isEmpty = uset.empty();

# 清空容器
uset.clear();

# 返回unordered_set中所有元素
return vector<int>(uset.begin(),uset.end())

• unorder_set.find()为什么需要与unorder_set.end()进行判断?

find() 方法总是返回一个迭代器，但这个迭代器可能指向实际存在的元素，也可能指向容器的结尾（end()）。因此，在使用 find() 的结果之前，必须先检查返回的迭代器是否有效（即不是 end()），以避免非法访问或未定义行为。这样的判断是必要的，因为它帮助开发者安全地处理不存在的情况，防止程序崩溃或者产生意外的结果.

本题的实现代码如下:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> res;		//存放结果
    unordered_set<int> s1(nums1.begin(),nums1.end());
    for (auto i : nums2) { //对nums2中元素进行迭代
        if (s1.find(i) != s1.end()) { //发现nums2中的元素在s1中出现过
            res.insert(i);
        }
    }
    return vector<int>(res.begin(),res.end());
}

4.两数之和

leetcode题号：1.两数之和

【题目描述】

在数组中找到两个元素的数值之和为目标值，返回这两个元素的下标

【题目分析】

很显然，直观的想法是使用暴力解，两层for循环寻找元素

如果使用哈希法，本题可以使用map。CPP中map有三种类型，而本题不需要有序输出，因此可以使用unordered_map即可。

unordered_map的基本操作

// 默认构造
std::unordered_map<int, std::string> myMap;

// 构造并初始化
std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

// 构造并指定初始容量
std::unordered_map<int, std::string> myMap(10);

// 构造并复制另一个 unordered_map
std::unordered_map<int, std::string> anotherMap = myMap;

# 插入元素
MyMap.insert({3."three"});
MyMap.insert(pair<int,int>(nums[i],i));

# 删除元素
myMap.erase(1);

# 查找元素
auto it = myMap.find(2); // 查找键为2的元素
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
}

# map中first。second属性
key=iter -> first;
value=iter -> second;

本题的代码实现如下:

vector<int>  twoSum(vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        auto iter= map.find(target - nums[i]);
        if (iter != map.end()) {
            return {iter->second, i};
            }
             map.insert(pair<int, int>(nums[i], i));
        }
   return {};

}

通过Map操作,时间复杂度降为$O(n)$,空间复杂度为$O(n)$.