您现在的位置是：首页 >技术杂谈 >算法10--哈希网站首页技术杂谈

原理

如果我们需要频繁地查找某一个元素，可以考虑使用哈希表，同时考虑到效率，如果可以简单的使用数组模拟哈希表，建议就直接使用数组模拟哈希表，没有必要使用容器。

经典例题

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

方法一：暴力求解
方法二：排序+二分
方法三：哈希，需要注意为了避免一些特殊情况，我们这里使用一边遍历查找，一边将已经查找的元素插入哈希表的方法。

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

        return {-1,-1};
    }
};

面试题 01.02. 判定是否互为字符重排

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

只需判断2个字符串中对应字符出现的个数是否相同就可以了。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int len1=s1.size();
        int len2=s2.size();
        if(len1!=len2)
        {
            return false;
        }
        int i=0;
        vector<int> count_s1(26,0);
        vector<int> count_s2(26,0);
        while(i<len1)
        {
            count_s1[s1[i]-'a']++;
            count_s2[s2[i]-'a']++;
            ++i;
        }
        i=0;
        while(i<26)
        {
            if(count_s1[i]!=count_s2[i])
            {
                return false;
            }
            ++i;
        }

        return true;
    }
};

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

方法一：排序+遍历
方法二：集合

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(auto e:nums){
            if(s.end()!=s.find(e)){
                return true;
            }
            s.insert(e);
        }

        return false;
    }
};

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int i=0-k;
        int j=0;
        for(;j<nums.size();++j,++i){
            if(s.end()!=s.find(nums[j])){
                return true;
            }
            s.insert(nums[j]);
            if(i>=0){
                s.erase(nums[i]);
            }
        }

        return false;
    }
};

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        string tmp;
        map<string,vector<string>> mp;
        for(auto& e:strs){
            tmp=e;
            sort(tmp.begin(),tmp.end());
            mp[tmp].push_back(e);
        }
        vector<vector<string>> ans;
        auto it=mp.begin();
        while(it!=mp.end()){
            ans.push_back(it->second);
            ++it;
        }

        return ans;
    }
};