算法刷题笔记--哈希表篇

哈希表

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
（英文名字为hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。

哈希函数

哈希表通过哈希函数将数据映射为索引，然后就可以通过查询索引下标快速查询数据

一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值

哈希碰撞

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。这种情况叫做哈希碰撞
哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

将发生冲突的数据储存在链表中

拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间

线性探测法

使用线性探测法，一定要保证tablesize大于datasize。 我们需要依靠哈希表中的空位来解决碰撞问题。

在遇到冲突的位置向下找一个空位放置冲突的信息

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

在c++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

数据小用数组，数据大用set，数据比较散用map

有效的字母异位词

数组在哈希表中的应用

两个数的交集

unordered_set查询和增删效率是最优的并且可以直接帮助使用者进行去重的操作

两数之和

为什么要用哈希法？
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

在遍历到一个数时判断组成target的一个元素是否遍历过，并在表中查找并返回下标

将遍历过的元素加到集合里，每遍历一个新的位置的时候就判断我们想要寻找的这个元素是否在这个集合里出现过，如果出现就是之前遍历过

为什么使用map
本题我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

map用来做什么
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的

map中key和value分别表示什么

判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

auto是一个提示符，提示编译器根据变量的值来推导变量的类型。
定义变量使用auto可让编译器自动推导变量类型；和范围for使用来遍历数组；加引用和范围for一起使用来修改数值。

使用auto定义变量时必须初始化，auto变量无法作为参数。在编译阶段编译器需要根据初始化表达式来推导auto的实际类型。因此auto并非是一种“类型”的声明，而是一个类型声明时的“占位符”，编译器在编译期会将auto替换为变量实际的类型。
map.find()返回值为一个迭代器

这段代码中的语句 if(iter!=map.end()) 的意思是检查迭代器 iter 是否指向了哈希表 map 的末尾位置。在c++中，unordered_map 的 find 方法返回一个迭代器，如果找到了目标元素，则返回指向该元素的迭代器；否则，返回指向哈希表末尾的迭代器 map.end()。

因此，if(iter!=map.end()) 这个条件语句的含义是：如果找到了符合条件的元素，即目标值与当前元素之差在哈希表中存在，则执行条件语句块内的代码。

class solution {
public:
    vector<int> twosum(vector<int>& nums, int target) {
        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{};
    }
};

四数相加ii

key:a+b的数值，value:a+b数值出现的次数
遍历大a和大b数组，统计两个数组元素之和，和出现的次数，放到map中

统计a+b+c+d = 0 出现的次数
在遍历大c和大d数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。

class solution {
public:
    int foursumcount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count=0;
        unordered_map<int,int> umap;
        for(int a=0;a<nums1.size();a++){
            for(int b=0;b<nums2.size();b++){
                umap[nums1[a]+nums2[b]]++;
            }
        }

        for(int c=0;c<nums3.size();c++){
            for(int d=0;d<nums4.size();d++){
                if(umap.find(0-(nums3[c]+nums4[d]))!=umap.end()){
                    count+=umap[0-(nums3[c]+nums4[d])];
                }
            }
        }
        return count;
    }
};

三数之和

重点：答案中不可以包含重复的三元组。
不能有重复的三元组，但三元组内的元素是可以重复的

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

class solution {
public:
    vector<vector<int>> threesum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){

            if(nums[i]>0){
                return result;
            }

            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int right=nums.size()-1;
            int left=i+1;
            while(right>left){
                if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }else{
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    while(right>left&&nums[right]==nums[right-1]){
                        right--;
                    }
                    while(right>left&&nums[left]==nums[left+1]){
                        left++;
                    }

                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

去重逻辑的思考
主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。
和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果是比较后一个，会直接将三元组中出现重复元素的情况pass掉，所以应选择比较前一个，即

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

快乐数

如果我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到1，因此返回false
因此要将每次的结果存储在哈希表中，检查是否有重复出现的现象，如果有就返回false，如果没有就继续遍历直到结果为1返回true

class solution {
public:
    int getsum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }

    bool ishappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum=getsum(n);
            if(sum==1){
                return true;
            }
            if(set.find(sum)!=set.end()){
                return false;
            }else{
                set.insert(sum);
            }
            n=sum;
        }
    }
};

赎金信

题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。

与有效字母的异位词该题的方法相似
（ps：感觉不是很能理解字符串相关的题目，该题和有效字母的异位词都需要以后再次学习）

class solution {
public:
    bool canconstruct(string ransomnote, string magazine) {
        int record[26]={0};
        for(int i=0;i<magazine.length();i++){
            record[magazine[i]-'a']++;
        }
        for(int j=0;j<ransomnote.length();j++){
            record[ransomnote[j]-'a']--;
            if(record[ransomnote[j]-'a']<0){
                return false;
            }
        }
        return true;
    }
};