代码随想录训练营day6|哈希表part01

@代码随想录@程序员Carl

哈希表理论基础

代码随想录（哈希表理论基础）

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

在看文章的时候还不太理解红黑树是什么。omg我这水平真感觉这一年白读了。

常见的三种哈希表结构：
    集合（set），数组，映射(map)。 

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

242.有效的字母异位词

代码随想录 (programmercarl.com)

242. 有效的字母异位词 - 力扣（LeetCode）

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

为什么是s[i]-'a'呢。因为假如s[i]=='a'，那a对应的下标就是0，这么推下去，z对应的下标就是25。

整个过程中，其实只要定义一个数组就行。最后判断这个数组中如果全部元素都为0，那么这两个输入的字符串就是有效的字母异位词。

思路弄懂了，代码写起来巨丝滑。

349.两个数组的交集

代码随想录 （两个数组的交集）

349. 两个数组的交集 - 力扣（LeetCode）

力扣的这道题现在改了条件数组结构要小于1000，这个时候就要用数组来解，而不是用集合（set）。但是之前没有这个限制，第一种解题思路是按之前的题目描述来做的，我们用set来解。为什么呢？因为上面说过“如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！”

使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复。

第二种解题思路是按力扣现在的题目限制，用数组来做。这时再来分析一下set的缺点：直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

注意：unordered_set的end()函数指向的是set最后一个元素之后的位置。

我觉得这道题比较难，视频看了两遍还比较蒙。可能是没开声音的原因吧。

202.快乐数

代码随想录 (programmercarl.com) （快乐数）

我没想到的是，这道题其实就是用set判断sum最后会不会重复出现。

1.两数之和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 （两数之和）

代码随想录 (programmercarl.com)（两数之和）

C++代码：

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 {};
    }
};

思路我已经清楚了，但是写代码时存在几个问题：

1.auto iter; 这是一个指针？！

   iter -> second ？！第一次见

2.第一次写道return {}；

3.map.insert(pair<int,int>(nums[i],i)这个也是第一次见