专题十四_哈希表_算法专题详细解答

目录

哈希表简介

1. 两数之和（easy）

解析：

解法一：暴力：

解法二：哈希O(N)

总结：

2. 判断是否互为字符重排（easy）

解析：

哈希：

总结：

3. 存在重复元素 I（easy）

解析：

总结：

4. 存在重复元素 II（easy）

解析：

解法一：暴力O(N^2)

解法二：哈希O(N)

总结：

5. 字⺟异位词分组（medium）

解析：

哈希：

总结：

哈希表相对来说还是比较简单的，但是这些提提远远不够，只能说给大家进行熟悉什么是哈希表，这里面所有的题目可能只是以后某个题目里面的一小步，所以我们慢点学，一定可以成功的~

---

哈希表简介

1.哈希表是什么？

存储数据的键值对 <int,int>

2.有什么作用？

“快速查找”某个元素                 时间：O(1)    空间：O(N)

3.什么时候用哈希表？

频繁查找一个某一个数的时候，二分（logN）

4.怎么用哈希表？

1.容器（哈希表）

2.用数组模拟简单哈希表     <index,n[index]>

1)字符串中的“字符”  26个字符

2)数据范围很小的时候

那么就就如例题，来彻底了解哈希算法：

1. 两数之和（easy）

解析：

解法一：暴力：

就是两层for循环遍历，每次都从当前位置的下一个数开始寻找，时间复杂度O(N^2)但是还是能过的。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        int a=0,b=0;
        int f=0;
        for(int i=0;i<nums.size();i++)
        {
            int a=i;
            for(b=a+1;b<nums.size();b++)
            {
                if(nums[a]+nums[b]==target)
                {
                    f=1;
                    v.push_back(a);
                    v.push_back(b);
                    break;
                }
            }
        }
        if(f==0)
        {
            v.push_back(0);
            v.push_back(0);
        }
        return v;
    }
};

解法二：哈希O(N)

这里利用哈希的查找特点，只需要在O(1)下就能找到当前值是否在hash表里面存在。

但是这里采用的是向前遍历的办法。为什么不采用向后遍历？那么就会多麻烦一步：

如果向后查找，首先就是将整个数组nums的值全部放入hash表里面，然后在遍历当前值的时候来确定是否有值满足能够保证加上当前值==target，那么此时举个例子：

假如当前值遍历到4，然后去计算x=target - nums[i] = 8 - 4 = 4；那么就说明要补充的值也是4，就去hash表里面进行查找，那么还是找到一个存在的值是自己，就会直接返回现在当前的下标返回两次。所以这里要单独判单是否会存在除了自己本身位置外的结果。

那么向下面这种代码的情况就只会去找当前位置之前的元素，因为当前位置以及后面的所有元素都还没有倍添加到hash表内，就不会出现重复查找同一个元素的情况。

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

总结：

题目不是很难，注意是要学会优化的思想来解决，合理运用哈希表的查找功能，及大优化时间复杂度。

2. 判断是否互为字符重排（easy）

题目意思真的太简单了，就一眼哈希

解析：

哈希：

1.就是先比较两个字符串的长度，如果连长度都不满足，那肯定就不构成重复的字符串

2.然后将s1的所有字符全部都添加到hash内，再让hash内s1字符出现的次数剪掉s2中的字符，如果出现<=0的情况却还遇到该字符，就说明s1 与 s2 相同字符的个数对不上，直接返回false

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int n=s1.size(),m=s2.size();
        if(n!=m) return false;
        unordered_map<char,int> hash;
        for(int i=0;i<n;i++)
            hash[s1[i]]++;

        for(int i=0;i<n;i++)
            if(hash[s2[i]]>0) hash[s2[i]]--;
            else return false;

        return true;
    }
};

总结：

题目真的不难，这题就真的很经典，适合熟练掌握hash的用法。

3. 存在重复元素 I（easy）

解析：

那么只需要判断当前值存在hash表里面的次数是否达到两次，如果是，就说明有重复的元素直接返回true

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++)
        {
            hash[nums[i]]++;
            if(hash[nums[i]]==2) return true;
        }
        return false;
    }
};

总结：

还是非常好对hash表有个熟练的理解，其实虽然这种题简单，但是只要学熟练了，这个步骤也就是苦难题里面的一小步，所以还得熟练掌握才行。

4. 存在重复元素 II（easy）

解析：

解法一：暴力O(N^2)

如果暴力的话这题就真的太麻烦了,必须要对数组的每一个数都要进行向后遍历一次来查找重复的值，绝对会超时的，那么就要想办法减少这种重复的操作。

解法二：哈希O(N)

题目意思只是说要找到两个相同的元素下标只差小于k那么我从nums数组第一个元素开始遍历的时候就要开始考虑hash当前元素只存当前元素的最大下标值，这样就可以做到，在访问到后面同一个元素的时候就会只用减去当前元素前一个位置的下标，不会出现在减去最前面元素的情况，因为当离我们最近的元素的最大下标减去后还不满足条件的话，就不会存在符合条件的下标了，就只能继续往后进行遍历。

那么每当不满足情况的时候，我就将当前元素的下标进行更新，更新成最大的下标，这样为下一次相减做准备。

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

总结：

这里只是运用了hash查找和更新值的效果，但主要是思想的体现，要想到能够怎么样进行算法的优化。将时间复杂度降低到O(N).

5. 字⺟异位词分组（medium）

题目意思还是比较简单的，就是将所有字符相同的字符串存在同一个vector<string>里面

解析：

哈希：

只需要遍历一遍数组，将每一个字符串进行排序，然后判断哈希表里面是否存在这个已经排序完成的字符串，如果是，就可以添加到ret已经出现过的位置即可，但是注意这里要添加的是原来未排序的字符串，所有要提前准备好一个s数组=strs来让他进行排序。

那么怎么添加到ret内呢？

这里就是用j来记录每一个不存在哈希表内的字符串时，让当前hash<string,int>进行j++，这样就能对应道ret这个二维数组内的第几行。，那么这时候就要对ret新添加一行：

ret.push_back(vector<string>());

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        int n=strs.size();
        vector<string> s=strs;
        unordered_map<string,int> hash;
        int j=0;
        for(int i=0;i<n;i++)
        {
            sort(s[i].begin(),s[i].end());
            if(hash.count(s[i])==0) hash[s[i]]=j++,ret.push_back(vector<string>());
            ret[hash[s[i]]].push_back(strs[i]);
        }
        return ret;
    }
};

总结：

哈希表相对来说还是比较简单的，但是这些提提远远不够，只能说给大家进行熟悉什么是哈希表，这里面所有的题目可能只是以后某个题目里面的一小步，所以我们慢点学，一定可以成功的~

总结一下吧~这一章对我的收获很大，希望对你也是！！！