Introduction to hash table

Hash table, also known as hash table, uses O(n) spatial complexity to store data, and maps the location through hash function, so as to realize the insertion, search, deletion and other operations with approximate O(1) time complexity.

The hash set in C + + is unordered_set to find out whether the element is in the collection. If you need to store both keys and values, you need to use unordered_map, which can be used to count frequency, record content, etc. If the elements are poor and the range is small, you can use a fixed size array to store or count the elements. For example, if we need to count the occurrence times of all letters in a string, we can use an array with a length of 26 for statistics, and its hash function is the position of letters in the alphabet, so that the spatial complexity can be reduced to a constant.

A simple hash table is implemented as follows:

template <typename T>
class HashTable {
private:
    vector<list<T>> hash_table;
    // hash function 
    int myhash(const T & obj) const {
    	return hash(obj, hash_table.size());
    }
    
public:
	// size is preferably a prime number
	HashTable(int size=31) {
        hash_table.reserve(size);
        hash_table.resize(size);
    }
	~HashTable() {}
	// Looks up whether the value exists in the hash table
    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();
    }
    // insert values
    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;
	}
	// Delete value
    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;
	}
};
// A simple hash function for integer implementation
int hash(const int & key, const int &tableSize) {
	return key % tableSize;
}

1 sum of two numbers

Given an array of integers, we know that the sum of two numbers is equal to the given value, and find the position of the two numbers.

Enter a one-dimensional integer array and a target value, and the output is a one-dimensional array with a size of 2, representing the positions of two numbers that meet the conditions.

Input: num = [2,7,11,15], target = 9
Output: [0,1]
Explanation: because num [0] + num [1] = = 9, return [0, 1].

Resolution:

You can use the hash table to store the traversed values and their positions. Each time you traverse to position I, find out whether target - num [i] exists in the hash table. If so, it indicates that the sum of the two values is 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 there are duplicate elements

Given an integer array, determine whether there are duplicate elements.

Enter a one-dimensional integer array, and the output is a Boolean value indicating whether there are duplicate elements in the array.

Input: [1,2,3,4]
Output: false

Resolution:

Hash table can be used for de duplication, which can quickly determine whether there are duplicate elements.

Traverse the array and insert all elements into the hash table. Before inserting, judge whether the element already exists. If it exists, it will directly return true. After traversing all arrays, if no duplicate elements are found, it will return 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 finding duplicates

Given an array num containing n + 1 integers, whose numbers are between 1 and n (including 1 and N), assuming that num has only one repeated integer, find out the repeated number.

Enter a one-dimensional integer array, and the output is an integer, indicating that there are duplicate elements in the array.

Input: num = [1,3,4,2,2]
Output: 2

Resolution:

This topic and 217 there are duplicate elements Questions are similar. Using a hash table can quickly determine whether there are duplicate elements.

Traverse the array and insert all elements into the hash table. Before inserting, judge whether the elements already exist. If they exist, directly return the value. If no duplicate elements are found after traversing all arrays, there are no duplicate elements in the array.

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 longest continuous sequence

Given an array of integers, find out how long the longest continuous sequence can be composed of numbers in this array.

Enter an array of integers and output an integer representing the length of a continuous sequence.

Input: num = [100,4200,1,3,2]
Output: 4
Explanation: the longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.

Resolution:

This problem can put all the numbers into a hash table, and then continuously take any value from the hash table. If the precursor element - 1 of the value does not exist, the current element is the starting point of the new sequence, and enumerate backward with the current value element as the starting point to find a continuous sequence.

Assuming that the last value of the continuous sequence of an enumeration is last, the length of the continuous sequence is last elem + 1. Through one-time traversal, find all continuous sequences in the array, and constantly update the longest sequence length.

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){
            // If elem - 1 does not exist, the current element is the starting point of the new sequence
            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 longest harmonic subsequence

A harmonious array means that the difference between the maximum and minimum values of elements in an array is exactly 1. Now, given an integer array nums, find the length of the longest harmonious subsequence among all possible subsequences.

Input an integer array and output an integer to represent the length of the harmonious subsequence.

Input: num = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: the longest harmonious subsequence is [3,2,2,2,3]

Resolution:

Ideas and of this topic 128 longest continuous sequence Same, or even simpler, because only a subsequence consisting of two elements with a difference of 1 needs to be considered.

Similarly, establish a hash table to count the frequencies of different values in the array, and then traverse the hash table to find the elements with a difference of 1, count the sum of their frequencies, and select the maximum value. Similarly, we only need to consider elem + 1, not elem - 1, because the previous value has been considered and does not need to be considered again.

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_multiset<int> hash;
        for(const auto num: nums){
            hash.insert(num);
        }
        int ans = 0;
        for(const auto elem: hash){
            int cnt = hash.count(elem);
            int nextCnt = hash.count(elem+1);
            if(nextCnt){
                ans = max(ans,cnt+nextCnt);
            }
        }
        return ans;
    }
};

697 degree of array

Given a non empty array nums, find the shortest continuous sub array with the same size as nums in nums, and return its length. The definition of group degree refers to the maximum frequency of any element in the array.

Input an integer array and output an integer to represent the shortest subsequence length consistent with the array degree.

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: the degree of the input array is 2, because the occurrence frequency of elements 1 and 2 is the largest, both of which are 2
The continuous subarrays with the same degree are as follows:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest continuous subarray [2, 2] has a length of 2, so it returns 2

Resolution:

This problem can directly use the hash table to count the frequency of elements in the array, and record the first and last positions of each element. Find out the element with the highest frequency. The subsequence between the first occurrence and the last occurrence is the shortest subsequence consistent with the degree of the array. It should be noted that the elements with the highest frequency may have multiple identical cases, and the case with the shortest sequence length among them should be saved.

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()){
                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 maximum number of points on a line

Given some points in two-dimensional coordinates, find the maximum number of points on the same line.

The input is a two-dimensional integer array representing the abscissa and ordinate of each point; The output is an integer representing the maximum number of points that meet the condition.

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: in the example, there are [[3,2], [4,1], [2,3], [1,4]] four points on y = 5 − x.

Resolution:

This question can establish a hash table to count the total number of points with the same slope. Because: a line can be uniquely determined by a point and slope. In addition, the absence of slope and repeated coordinates need to be considered.

The double loop is used to traverse the slope of each point and other points, the outer loop traverses all points, and the inner loop counts the number of points with the same slope. When traversing each point, for the point at position i in the array, we only need to consider the point after i, because the point before i has considered i.

First, we should consider the case that the slope does not exist, that is, the x coordinates of the points are the same; If not only the x coordinate but also the y coordinate are the same, the two points are duplicate coordinates.

Then, considering the general situation, that is, the existence of slope, you only need to traverse one by one, calculate the slope between two points and save it in the hash table.

Finally, the line with the most points in the line related to the current point is calculated according to the result of one traversal.

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

            // Straight line with non-existent slope related to (i,j)
            ans = max(ans,same_x);
            // A straight line where the slope stored in the hash table related to (i,j) exists
            for(const auto [rate,count]: hash){
                ans = max(ans,same+count);
            }
            hash.clear();
        }
        return ans;
    }
};

reference material

LeetCode 101: easily brush questions with you (C + +) Chapter 11 wonderful use of data structure