当前位置：首页 > article >正文

[代码随想录06]哈希表的使用，有效字母异位词，两数组交集，快乐数，两数之和

article 2024/12/3 18:16:47

前言

哈希表是什么？一句话带你理解，简单来说我们对于杂乱的数据，怎么快速找到数据，如何做呢？一般的做法就是遍历复杂度为o(N)去找寻一个数据，但是吧，我们这样思考的话，还是花了大量时间去检查其他元素是否存在这个集合里面，如何优化呢？我们通过特定的计算把每个值都用特定的值来唯一表示起来，我们每次查询只需要通过计算，然后看这个特定的结构里面是否有对应映射的值，这种情况下，我们的查询效率就能达到o(1),这个做法也就是前文提到的空间换时间。

有了特定的索引值去表示，这个数据是否存在，那么就会存在哈希冲突，哈希冲突就是多个值对应一个索引值，我们就无法判断。这个时候一般的做法就是再哈希，线性探测（闭散列），拉链法（开散列）拉一个链表在冲突的地方。

HashTable的三种结构：①数组 ②set ③unordered_map对应底层的数据结构也是不一样的。

题目链接

242. 有效的字母异位词 - 力扣（LeetCode）

349. 两个数组的交集 - 力扣（LeetCode）

202. 快乐数 - 力扣（LeetCode）

1. 两数之和 - 力扣（LeetCode）

一、有效的字母异位词

思路：三个for循环搞定，一个for循环就是把数据存进去，第二个for循环就是把数据取走，第三个for循环就是检查还有没有数据在里面。就能判定字母是否是异位词。

tips：使用数组可以在空间的效率上有提升。这道题建议使用数组能起到联系的作用。

class Solution {
public:
//使用数组
     bool isAnagram1(string s, string t) {
        if(s.length()!=t.length())return false;
        int records[26]={0};
        for(auto it:s)  records[it-'a']++;
        for(auto it:t)  records[it-'a']--;
        for(auto it:records){
            if(it!=0)return false;
        }
        return true;
    }
//使用map表
    bool isAnagram2(string s, string t) {
        if(s.length()!=t.length())return false;
        unordered_map<int,int>dic;
        for(auto it:s)  dic[it]+=1;
        for(auto it:t)  dic[it]-=1;
        for(auto it:dic){
            if(it.second!=0)return false;
        }
        return true;
    }
};

二、两个数组的交集

思路:两个数组的交集，我们首先想到的就是用哈希的思想去找到两个共同元素，这样就强迫我们私用不能重复的结构set，然后用一个对结果集合进行去重，一个就是单纯用来存放一组数据的，方便我们去遍历查找，最后我们使用。

//使用set去重，然后循环遍历查找入结果集。
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int>result_set;
        unordered_set<int>nums_set(nums1.begin(),nums1.end());
        for(auto num:nums2){
            if(nums_set.find(num)!=nums_set.end())result_set.insert(num);
        }
        return vector<int>(result_set.begin(),result_set.end());
    }

leetcode 对数值的大小修订之后我们就可以使用数组来解决这个问题。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int>result_set;
        int hash[1005]={0};
        for(auto num:nums1){
            hash[num]=1;
        }
        for(int num:nums2){
            if(hash[num]==1)result_set.insert(num);
        }
        return vector<int>(result_set.begin(),result_set.end());
    }

三、快乐数

思路:题目说了直到1为止就会跳出循环。

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

使用快慢指针的方法,循环两者终将会相遇。

int bitsum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
    bool isHappy(int n) {
       int slow=n,fast=n;
       do{
        slow=bitsum(slow);
        fast=bitsum(fast);
        fast=bitsum(fast);
       }while(slow!=fast);
       return slow==1;
    }

四、两数之和

哈希表的精髓所在:直接使用target-num[i]去查找一个元素的是否存在集合中。

vector<int> twoSum(vector<int>& nums, int target) {
       int n=nums.size();
       unordered_map<int,int>mp;
       for(int i=0;i<n;i++)
       {
        auto it=mp.find(target-nums[i]);
        if(it!=mp.end()) return {it->second,i};
        mp[nums[i]]=i;
       }
       return {};
    }