哈希leetcode-1

目录

1前言

2.例题

 2.1两数之和

2.2判断是否互为字符重排

2.3存在重复元素1

2.4存在重复元素2

2.5字母异位词分组

1前言

哈希表主要是适合于快速查找某个元素（O(1)）

当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n)

一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。

最简单的比如数组模拟字符存储，只要开26个char的数组即可。

用数组模拟速度比用容器哈希快。但是有局限性（主要是针对数据范围小的时候）

2.例题

 2.1两数之和

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

利用哈希表，存储当前位置数字前的所有数字。

这样可以直接查询需要的数字。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        unordered_map<int,int>hash1;
        for(int i=0;i<n;i++)
        {
            if(hash1.count(target-nums[i]))
            {
                return {hash1[target-nums[i]],i};
            }
            hash1[nums[i]]=i;
        }
        return {};
    }
};

2.2判断是否互为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

思路1

利用两个哈希表，一个存s1中字符出现个数，一个存s2中字符出现个数

然后比较两个哈希表即可

注意，这题是字符，所以直接用数组模拟即可。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if(s1.size()!=s2.size())return false;
        int hash1[26]={0};
        int hash2[26]={0};
        //统计s1
        for(auto a:s1)
        {
            hash1[a-97]++;
        }
        //统计s2
        for(auto a:s2)
        {
            hash2[a-97]++;
        }
        //比较
        for(int i=0;i<26;i++)
        {
            if(hash1[i]!=hash2[i])return false;
        }
        return true;
    }
};

思路2

区别不大。只用1个哈希表。遍历s2的时候，同步更新

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if(s1.size()!=s2.size())return false;
        int hash1[26]={0};
        for(auto a:s1)
        {
            hash1[a-97]++;
        }
        for(auto a:s2)
        {
            hash1[a-97]--;
            if(hash1[a-97]<0)return false;
        } 
        //比较神奇的是，如果加上这段for循坏，能过且0ms，但是如果不加，4ms能过
        for(int i=0;i<26;i++)
        {
            if(hash1[i]>0)return false;
        }
        return true;
    }
};

2.3存在重复元素1

217. 存在重复元素 - 力扣（LeetCode）

哈希表统计数字出现即可。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int>hash1;
        for(auto s:nums)
        {
            hash1[s]++;
            if(hash1[s]>=2)return true;
        }
        return false;
    }
};

2.4存在重复元素2

219. 存在重复元素 II - 力扣（LeetCode）

直接用哈希表判断即可

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int>hash1;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            if(hash1.count(nums[i]))
            {
                if(i-hash1[nums[i]]<=k)return true;
            }
            hash1[nums[i]]=i;
        }
        return false;
    }
};

2.5字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）

思路就是利用排序，统计是否是异位词

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>>hash1;
        for(auto x:strs)
        {
            auto tmp=x;
            sort(tmp.begin(),tmp.end());
            hash1[tmp].push_back(x);
        }
        vector<vector<string>>ret(0);
        for(auto x:hash1)
        {
            ret.push_back(x.second);
        }
        return ret;
    }
};