06 哈希表

​ 哈希表，又称散列表，使用 O(n) 空间复杂度存储数据，通过哈希函数映射位置，从而实现近似 O(1) 时间复杂度的插入、查找、删除等操作。 ​ C++ 中的哈希集合为 unordered_set，可以查找元素是否在集合中。如果需要同时存储键和值，则需要用 unordered_map，可以用来统计频率，记录内容等等。如果元素有穷，并且范围不大，那么可以用一个固定大小的数组来存储或统计元素。例如我们需要统计一个字符串中所有字母的出现次数，则可以用一个长度为 26 的数组来进行统计，其哈希函数即为字母在字母表的位置，这样空间复杂度就可以降低为常数。 ​ 一个简单的哈希表的实现如下：

template <typename T>
class HashTable {
private:
    vector<list<T>> hash_table;
    // 哈希函数
    int myhash(const T & obj) const {
    	return hash(obj, hash_table.size());
    }
    
public:
	// size最好是质数
	HashTable(int size=31) {
        hash_table.reserve(size);
        hash_table.resize(size);
    }
	~HashTable() {}
	// 查找哈希表是否存在该值
    bool contains(const T & obj) {
        int hash_value = myhash(obj);
        const list<T> & slot = hash_table[hash_value];
        std::list<T>::const_iterator it = slot.cbegin();
        for (; it != slot.cend() && *it != obj; ++it);
        return it != slot.cend();
    }
    // 插入值
    bool insert(const T & obj) {
        if (contains(obj)) {
        	return false;
    	}
        int hash_value = myhash(obj);
        std::list<T> & slot = hash_table[hash_value];
        slot.push_front(obj);
        return true;
	}
	// 删除值
    bool remove(const T & obj) {
        list<T> & slot = hash_table[myhash(obj)];
        auto it = find(slot.begin(), slot.end(), obj);
        if (it == slot.end()) {
        	return false;
        }
		slot.erase(it);
		return true;
	}
};
// 一个简单的对整数实现的哈希函数
int hash(const int & key, const int &tableSize) {
	return key % tableSize;
}

1 两数之和 (opens new window)

给定一个整数数组，已知有且只有两个数的和等于给定值，求这两个数的位置。

输入一个一维整数数组和一个目标值，输出是一个大小为 2 的一维数组，表示满足条件的两个数字的位置。

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解析：

​ 可以利用哈希表存储遍历过的值以及它们的位置，每次遍历到位置 i 的时候，查找哈希表里是否存在 target - nums[i]，若存在，则说明这两个值的和为 target。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        vector<int> ans;
        for(int i=0;i<nums.size();++i){
            int num = nums[i];
            auto pNum = hash.find(target-num);
            if(pNum != hash.end()){
                ans.push_back(i);
                ans.push_back(pNum->second);
                break;
            }else{
                hash[num] = i;
            }
        }
        return ans;
    }
};

217 存在重复元素 (opens new window)

给定一个整数数组，判断是否存在重复元素。

输入一个一维整数数组，输出是一个布尔值表示数组中是否存在重复元素。

输入: [1,2,3,4]
输出: false

解析：

​ 哈希表可以用于去重复，可以快速判断是否存在重复元素。

​ 遍历数组将所有元素都插入哈希表中，插入之前判断元素是否已经存在，如果存在则直接返回 true，遍历全部数组之后没有发现重复元素则返回 false。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for(const auto num: nums){
            if(hash.count(num)){
                return true;
            }
            hash.insert(num);
        }
        return false;
    }
};

287 寻找重复数 (opens new window)

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），假设 nums 只有一个重复的整数 ，找出这个重复的数 。

输入一个一维整数数组，输出是一个整数表示数组中存在重复的元素。

输入：nums = [1,3,4,2,2]
输出：2

解析：

​ 本题和217 存在重复元素 (opens new window)题相似，使用哈希表可以快速判断是否存在重复元素。

​ 遍历数组将所有元素都插入哈希表中，插入之前判断元素是否已经存在，如果存在则直接返回该值，遍历全部数组之后没有发现重复元素，则数组不存在重复元素。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for(auto num: nums){
            if(hash.count(num)){
                return num;
            }
            hash.insert(num);
        }
        return 0;
    }
};

128 最长连续序列 (opens new window)

给定一个整数数组，求这个数组中的数字可以组成的最长连续序列有多长。

输入一个整数数组，输出一个整数，表示连续序列的长度。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

解析：

​ 本题可以把所有数字放到一个哈希表，然后不断地从哈希表中任意取一个值，如果该值的前驱 elem - 1 不存在那么当前元素是新的序列起点，以当前值 elem 为起点向后枚举寻找连续序列。

​ 假设一次枚举的连续序列最后一个值为 last，那么该连续序列的长度为 last-elem+1。通过一遍遍历寻找数组中的所有连续序列，并不断更新最长序列长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for(const auto& num: nums){
            hash.insert(num);
        }
        int ans = 0;
        for(const auto elem: hash){
            // 如果 elem - 1 不存在那么当前元素是新的序列起点
            if(hash.find(elem-1)==hash.end()){
                int cur = elem;
                while(hash.find(cur+1)!=hash.end()){
                    ++cur;
                }
                ans = max(ans,cur-elem+1);
            }
        }
        return ans;
    }
};

594 最长和谐子序列 (opens new window)

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。现在，给定一个整数数组 nums ，在所有可能的子序列中找到最长的和谐子序列的长度。

输入一个整数数组，输出一个整数，表示和谐子序列的长度。

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

解析：

​ 本题的思路和128 最长连续序列 (opens new window)一样，甚至更加简单，因为只需要考虑由两个相差为 1 的元素组成的子序列。

​ 同样的建立一个哈希表用于统计不同值在数组中的频数，然后遍历哈希表找到相差为 1 的元素统计他们频数之和选取最大值。同样的，我们只需要考虑 elem + 1，而不需要回过头来考虑 elem - 1，因为之前的值已经考虑了，不需要重复考虑。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int> hash;
        // 统计频数
        for(const auto num: nums){
            if(hash.find(num)==hash.end()){
                hash[num] = 1;
            }else{
                ++hash[num];
            }
        }
        // 计算最长和谐子序列
        int ans = 0;
        for(const auto [elem,cnt]: hash){
            if(hash.find(elem+1)!=hash.end()){
                ans = max(ans,cnt+hash[elem+1]);
            }
        }
        return ans;
    }
};

697 数组的度 (opens new window)

给定一个非空数组 nums，在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。组的度的定义是指数组里任一元素出现频数的最大值。

输入一个整数数组，输出一个整数，表示与数组度一致的最短子序列长度。

输入：[1, 2, 2, 3, 1] 输出：2 解释：输入数组的度是2，因为元素1和2的出现频数最大，均为2. 连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组[2, 2]的长度为2，所以返回2.

解析：

​ 本题可以直接使用哈希表统计数组中元素出现的频次，并记录每个元素第一次出现和最后一次出现的位置。找出出现频次最高的元素，它第一次出现到最后一次出现两个位置之间的子序列就是与数组度一致的最短子序列。需要注意的是，要考虑到频次最高的元素可能存在多个相同的情况，这时保存他们之中序列长度最短的情况。

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> hash;
        for(int i=0;i<nums.size();++i){
            int num = nums[i];
            if(hash.find(num)==hash.end()){
                // 这里用列表初始化，如果直接使用索引访问会出错，应为未初始化vector
                hash[num] = {1,i,i};
            }else{
                hash[num][0]++;
                hash[num][2] = i;
            }
        }

        int maxCnt = 0;
        int ans = 0;
        for(const auto [num, vec]: hash){
            if(maxCnt < vec[0]){
                maxCnt = vec[0];
                ans = vec[2] - vec[1] + 1;
            }else if(maxCnt == vec[0]){
                ans = min(ans,vec[2] - vec[1] + 1);
            }
        }
        return ans;
    }
};

149 直线上最多的点数 (opens new window)

给定一些二维坐标中的点，求同一条线上最多由多少点。

输入是一个二维整数数组，表示每个点的横纵坐标；输出是一个整数，表示满足条件的最多点数。

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
解释：样例中，y = 5 − x 上有[[3,2],[4,1],[2,3],[1,4]]四个点。

解析：

​ 本题可以建立一个哈希表，统计同一斜率的点一共有多少个。因为：一条线可以由一个点和斜率唯一确定。另外需要考虑到斜率不存在和重复坐标的情况。

​ 采用双重循环遍历每一个点与其他点的斜率，外循环遍历所有点，内循环统计斜率相同的点的个数。在遍历每个点时，对于数组中位置 i 的点，我们只需要考虑 i 之后的点即可，因为 i 之前的点已经考虑过 i 了。

​ 首先我们要考虑斜率不存在的情况，即点的 x 坐标相同；如果不仅 x 坐标相同，y 坐标也相同，那么这两个点为重复坐标。

​ 然后，考虑一般情况，即斜率存在的情况，只需要逐个遍历，计算两点之间的斜率并保存到哈希表中即可。

​ 最后根据一次遍历的结果计算与当前点有关的直线中最多点数的直线。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        unordered_map<double,int> hash;
        int ans = 0;
        for(int i=0;i<points.size();++i){
            int same_x = 1, same = 1;
            for(int j = i+1;j<points.size();++j){
                // 斜率不存在的情况
                if(points[i][0] == points[j][0]){
                    ++same_x;
                    // 两个点为重复坐标
                    if(points[i][1] == points[j][1]){
                        ++same;
                    }
                }else{
                    // 一般情况
                    double dy = points[j][1] - points[i][1];
                    double dx = points[j][0] - points[i][0];
                    ++hash[dy/dx];
                }
            }

            // 与(i,j)相关斜率不存在的直线
            ans = max(ans,same_x);
            // 与(i,j)相关哈希表中保存的斜率存在的直线
            for(const auto [rate,count]: hash){
                ans = max(ans,same+count);
            }
            hash.clear();
        }
        return ans;
    }
};