哈希表理论基础总结：

什么是哈希表，哈希表是根据关键码的值而直接进行访问的数据结构。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。  

例如要查询一个名字是否在这所学校里，要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了Hash Function，也就是哈希函数。

哈希函数

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashCode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？ 

此时为了保证映射出来的索引数值都落在哈希表上，我们会再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置。

接下来哈希碰撞登场。

哈希碰撞

如图所示，小李和小王都映射到了索引下标'1'的位置，这一现象叫做哈希碰撞。

 一般哈希碰撞有两种解决办法，拉链法和线性探测法。 

拉链法

刚刚小李和小王在索引'1'的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了。

（数据规模是dataSize，哈希表的大小为tableSize）

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

线型探测法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

常见的三种哈希结构 

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

• 数组
• set（集合）
• map（映射） 

这里数组就没啥可说的了，我们来看一下set。

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

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(log n)	O(log n)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

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

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可以重复	key不可修改	O(log n)	O(log n)
std::multimap	红黑树	key有序	key可以重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

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的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std::map也是一样的道理。

总结一下，当我们遇到了要快速判断一个元素是否出现在集合里的时候，就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或是map来存放数据，才能实现快速的查找。 

哈希表的经典题目：

/*
    思路分析：定义一个数组用来记录字符串s里的字符出现的次数
*/
class Solution {
public:
    bool isAnagram(string s, string t) {
        int len = s.size();
        if(len != t.size())
            return false;
        int arr[26];
        for(int i = 0;i < len;++i) {
            arr[s[i] - 'a']++;
            arr[t[i] - 'a']--;
        }
        for(int i = 0;i < 26;++i) {
            if(arr[i] != 0)
                return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res;    // 存放结果，之所以用set是为了给结果去重
        unordered_set<int> filter_num(nums1.begin(),nums1.end());
        for(int num : nums2) {
            // 发现 nums2 的元素在 filter_num 里出现过
            if(filter_num.find(num) != filter_num.end()) {
                res.insert(num);
            }
        }
        return vector<int>(res.begin(),res.end());
    }
};

/*
    思路分析：题目中说了会 '无限循环'，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
             所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false
*/
class Solution {
public:
    int getNum(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> res;
        while(1) {
            int sum = getNum(n);
            if(sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环，立刻return false
            if(res.find(sum) != res.end()) {
                return false;
            } else {
                res.insert(sum);
            }
            n = sum;
        }
    }
};

/* 
    思路分析：暴力解法这里就不过多赘述了，时间复杂度O(n^2)
             本题需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去查询这个集合，某元素是否遍历过，也就是是否出现在这个集合
*/
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.首先定义一个 unordered_map，key存放a和b两数之和，value存放两数之和出现的次数
             2.遍历A、B数组，统计两个数组元素之和及出现次数，放到map中
             3.定义变量 'count' 用来统计 a + b + c + d = 0 出现的次数
             4.再遍历C、D数组，找到如果 0 - (c + d)在map中出现过的话，就用count把map中key对应的value（出现次数）统计出来
             5.最后返回统计值 'count' 即可
*/
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> abSum;
        for(int a : nums1) {
            for(int b : nums2) {
                abSum[a + b]++;
            }
        }

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

/*
    思路分析：1.暴力解法：两层for循环，在ransomNote中找到和magazine相同的字符则删除这个字符，最后如果ransomNote为空，则说明magazine的字符可以组成ransomNote
             2.哈希解法：用一个长度为26的数组来记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母
*/
1.暴力解法
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};

2.哈希解法
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过record数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

/*
    思路分析：1.哈希解法：两层for循环确认a和b的数值，可以使用哈希法来确定0-(a+b)是否在数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。把符合条件的三元组放进vector中，然后再去重，是非常费时的，去重的过程不好处理。
             2.双指针法：首先将数组排序，然后一层for循环，i从下标0的地方开始，同时定一个下标left定义在i+1的位置上，定义下标right再数组结尾的位置上。依然还是在数组中找到abc使得'a + b + c = 0',我们这里相当于 'a = nums[i], b = nums[left], c = nums[right]'。
*/
1.哈希解法
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重
                } else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

2.双指针法
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n < 3) return res;

        sort(nums.begin(),nums.end());

        for(int i = 0;i < n - 2;++i) {
            // 跳过重复元素
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if(sum == 0) {
                    res.push_back({ nums[i],nums[left],nums[right] });

                    // 跳过重复元素
                    while(left < right && nums[left] == nums[left + 1]) ++left;
                    while(left < right && nums[right] == nums[right - 1]) --right;

                    ++left;
                    --right;
                } else if(sum < 0) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return res;
    }
};

/*
    思路分析：四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出 'nums[k] + nums[i] + nums[left] + nums[right] == target' 的情况，三数之和的时间复杂度为 O(n^2)，四数之和的时间复杂度是 O(n^3)。那么一样的道理，五数之和、六数之和等等都采用这种解法。
*/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对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;
    }
};