526互联

代码随想录刷题记录——哈希表

发布时间 2023-09-07 10:58:45作者: DaxiaWan

哈希表基础知识

哈希表（Hash table）又称散列表，是根据关键码的值而直接进行访问的数据结构
哈希表一般用来快速查询元素a是否在集合B中，O(1)时间复杂度即可做到，枚举的话则是O(n)
哈希函数hashFunction(x)：将输入x映射为哈希表上的索引，之后通过查询索引下标即可快速查询x
哈希碰撞：当不同输入映射到同一索引时，即发生哈希碰撞，解决办法：1）拉链法； 2）线性探测法
- 拉链法：在冲突索引处再加个链表
- 线性探测法：必须tableSIze>dataSize

常见的三种哈希结构
- 数组
- set(集合)
- map(映射)
哈希表特性：牺牲空间换取时间

242.有效的字母异位词

题目描述：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

思路：record数组，记录字符出现次数

C++ AC code：

#include<iostream>
#include<string>
using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0 };
        for(int i=0; i<s.size();i++){
            record[s[i]-'a']++;
        }
        for(int i=0;i<t.size();i++){
            record[t[i]-'a']--;
        }
        for(int i=0; i<26; i++){
            if(record[i]!=0) return false;
        }
        return true;
    }
};

View Code

349. 两个数组的交集

题目描述：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

思路：

　　掌握unordered_set数据结构的使用

C++ AC code：

#include<unordered_set>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> ans;
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        for(int num: nums2){
            if(nums1_set.find(num)!=nums1_set.end()){
                ans.insert(num);
            }
        }
        return vector<int>(ans.begin(), ans.end());
    }
};

View Code

第202题. 快乐数

C++ AC code：

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int getSum(int x){
        int sum = 0;
        while(x){
            sum += (x%10)*(x%10);
            x = x/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        int sum = getSum(n);
        while(1){
            if(sum==1) return true;
            if(set.find(sum)!=set.end()) return false;
            set.insert(sum);
            sum = getSum(sum);
        }
    }
};

unordered_set集合常用函数：

unordered_set是C++ STL中提供的一个无序集合容器，它支持快速的元素查找、插入和删除操作。以下是unordered_set常用的函数：

insert()：向unordered_set中插入一个元素，如果该元素已经存在，则不会重复插入，并返回true；否则插入成功，并返回false。
erase()：从unordered_set中删除指定元素的第一个匹配项，并返回删除的个数。
count()：返回unordered_set中指定元素的个数。
find()：查找unordered_set中是否存在指定元素，如果存在则返回指向该元素的迭代器，否则返回end迭代器。
empty()：判断unordered_set是否为空，为空返回true，否则返回false。
size()：返回unordered_set中元素的个数。
max_load_factor()：获取当前unordered_set的最大负载因子，即元素个数与桶数的比值。
bucket_count()：返回unordered_set中的桶数。

以上由AI生成。

1.两数之和

掌握unordered_map相关操作

C++ AC code：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;//值为nums[i]的key不存在时插入，否则更新key对应的值
        }
        return {};
    }
};

第454题. 四数相加II

a+b+c+d=0,map存放<所有a+b和sum1,sum1出现次数>,再计算所有c+d,map.find(0-c-d)，查找key是否在map中，在则count+map[key]。

C++ AC code：

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        for(int a: nums1){
            for(int b: nums2){
                map[a+b]++;
                //key:a+b 存在时，对应value+1，否则，插入且值为1
                // map[a+b];
                //map[a+b]=map[a+b]+1;
                //‘operator[]操作符’:访问不存在key时自动插入且初始化值为0
                // if(map.find(a+b)!=map.end()){
                //     map[a+b]++;
                // }
                // else{
                //     map[a+b]=1;
                // }
            }
        }
        int ans = 0;
        for(int c: nums3){
            for(int d: nums4){
                if(map.find(0-(c+d))!=map.end()){
                    ans += map[0-(c+d)];
                }
            }
        }
        return ans;
    }
};

383. 赎金信

C++ AC code：

　　版本一：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> map;
        for(char ch: magazine){
            map[ch]++;
        }
        for(char ch: ransomNote){
            if(map.find(ch)!=map.end()&&map[ch]>0){
                map[ch]--;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

　　版本二：优化

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int a[26] = {0};
        for(char ch: magazine){
            a[ch-'a']++;
        }
        for(char ch: ransomNote){
            if(a[ch-'a']>0){
                a[ch-'a']--;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

第15题. 三数之和

暴力求解：O(n^3)

思路：

双指针
去重

C++ AC code：

时间复杂度：O(n^2)

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());//原地排序
        vector<vector<int>> ans;
        for(int i=0;i<nums.size();i++){//a+b+c中的a
            if(nums[i]>0){
                return ans;
            }
            //a去重，因为答案中不可以包含重复三元组
            if(i>0 &&nums[i]==nums[i-1]){
                continue;
            }
            for(int left=i+1, right=nums.size()-1;left<right;){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else if(sum==0){
                    ans.push_back({nums[i],nums[left],nums[right]});
                    // ans.push_back(vector<int> {nums[i],nums[left],nums[right]});
                    while(left<right&&nums[left]==nums[left+1]) left++;//b去重
                    while(left<right&&nums[right]==nums[right-1]) right--;//c去重
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }

第18题. 四数之和

暴力求解：O(n^4)

思路：

双指针
去重
剪枝

C++ AC code：

时间复杂度：O(n^3)

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        // for(int i=0;i<nums.size()-3;i++){   //a+b+c+d,遍历a
        for(int i=0;i<nums.size();i++){   //a+b+c+d,遍历a
            //剪枝
            if(nums[i]>target&&nums[i]>=0){
                break;
            }
            //a去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            // for(int j=i+1;j<nums.size()-2;j++){     //遍历b
            for(int j=i+1;j<nums.size();j++){     //遍历b
                //剪枝
                if(nums[i]+nums[j]>target&&nums[j]>=0){     //这里a+b不会溢出，int：2^31-1==2.e9;
                    break;
                }
                //去重
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                for(int left=j+1, right=nums.size()-1;left<right;){
                    //双指针
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];//防溢出
                    if(sum>target){
                        right--;
                    }
                    else if(sum<target){
                        left++;
                    }
                    else{
                        ans.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left<right&&nums[left]==nums[left+1]) left++;//c去重
                        while(left<right&&nums[right]==nums[right-1]) right--;//d去重
                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
};

哈希表总结

哈希表用来快速判断一个元素是否出现在集合里
知道哈希函数和哈希碰撞
- 哈希函数：将传入的key映射到符号表索引中
- 哈希碰撞：处理多个key映射到相同索引时的场景，普遍方式是拉链法和线性探测法
三种常见哈希结构
- 数组：
- 集合set：unordered_set(无序)、set（有序）、multiset（有序、可重复）
- 映射map：每个元素是<key, value>组，unordered_map、map\multimap
- 进阶：熟悉上述数据结构的底层实现
根据题目类型选择用数组、集合或映射

随想录随想代码

随想录随想代码day

随想录随想代码动态

随想录随想代码part

随想录随想算法代码

之和随想录随想代码

随想录数组随想代码

随想录队列随想代码

随想录随想代码day3

随想录随想元素代码