哈希入门题目解决(C++)必看-创新互联

哈希入门题目解决(C++) 必看

学完本文，你需要自己解决：

创新互联公司专注于企业营销型网站、网站重做改版、莒县网站定制设计、自适应品牌网站建设、H5场景定制、成都做商城网站、集团公司官网建设、外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为莒县等各大城市提供网站开发制作服务。

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

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

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

202. 快乐数 - 力扣（LeetCode）

454. 四数相加 II - 力扣（LeetCode）

最近刚开始看STL源码剖析，才知道啥叫一入C++深似海，当然扯远了，hash类不仅面试常考，而且我认为难度是不次于RBTree和AVL等数据结构的。 至于hash类的实现，读者感兴趣的可以看STL源码剖析，本文是对std::unordered_set和unordered_map的应用，只是为了教授读者如何使用常见的接口。

hash： 查询和删除是 o(1)的复杂度 记住这一点就可以了

常见的接口一定要掌握的，第一重要的就是[]。这个运算符对于hash有特殊的意义。官方文档写：

Ifkmatches the key of an element in the container, the function returns a reference to its mapped value.

Ifkdoes not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

总结[]的三大功能就是 ： 1：找(如果存在) 2.插入(key不存在) 3 改

为了避免抽象我用一段简单代码解释下：

unordered_mapmymap;
	mymap["jack"] = 1;
	mymap["lisa"] = 1; //插入
	mymap["james"] = 0;

	int status = mymap["jack"]; //找
	cout<< status<< endl;

	mymap["james"] = 1; //改
	cout<< mymap["james"]<< endl;

另一个常见接口是find，具体内容大家看文档就可以了，用来查找的，有一点我给新手读者强调下，find找不到会返回end的迭代器，这点要注意，我们经常要利用。

简单模式

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

这道题其实很好的反映了哈希思想，其实哈希的本质就是映射，这道题我们没有必要用stl的hash解决，我就用数组了，每一个字母我们映射到对应的位置，一个加一个减，最后数组含有非0就是false。

class Solution {
public:
    bool isAnagram(string s, string t) {
    vectorres(26, 0);

    for (auto e: s)
    {
        res[e - 'a']++;
    }

    for (auto e : t)
    {
        res[e- 'a']--;
    }

    for (auto e : res)
    {
        if (e != 0)
            return false;
    }

    return true;
    }
};

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

这道题我们想一下，找交集，可以用两层for，挨个去比对。我们有没有更好的办法？ 其实就是哈希，我们先用set去重以后，遍历一个数组，然后用find接口去找，因为在哈希中find是o(1)的对吧，这样就一层for就解决了，比较简单，直接上代码了。

class Solution {
public:
    vectorintersection(vector& nums1, vector& nums2) {
    unordered_setres;
    unordered_setset(nums1.begin(), nums1.end());

    

    for (auto e : nums2)
    {
        if (set.find(e) != set.end())
        {
            res.insert(e);
        }
    }
    return vector(res.begin(), res.end());
    }
};

这里我唯一要说的就是，很多新手很纳闷这个find咋等于end去了啊，注意，我再次强调，文档一定好好看，find找不到的时候会返回end的迭代器。 所以这句代码的意思就是我们在set里面找到了e，所以加入到结果集。

202. 快乐数 - 力扣（LeetCode）

这个题也比较有意思。题目说有可能会无限循环也到不了1，很多读者理解不了这啥意思。 我举个例子啊，比如2， 下一步是4， 16， 37， 58，89，145，42，18，65，61，37. 到这我们发现了一个重要的问题，凡是这个不是快乐数的啊，我们算着算着一定会倒回去，不信的你可以自己再举例试试啊。 所以很简单，我们直接开一个set，用find找是吧。

bool isHappy(int n) {
    unordered_setres;

    while (1)
    {
        int sum1 = sum(n);
        if (sum1 == 1)
            return true;
        else 
        {
            if (res.find(sum1) != res.end())
            {
                return false;
            }
            else
                res.insert(sum1);
        }

        n = sum1;
    }

这里怎么求每位数的平方就是sum函数我就不写了，读者应该都会。

几个数字的和

这里这两个题比之前的有些难度还是。

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

这个题算俩数的和，咋算呢，其实本质我还是利用这个find，但是以前咱们都是find这个数对吧，现在应该find啥啊，其实就是target-我们当前这个数，俩数是不是就能凑出来了啊。

class Solution {
public:
    vectortwoSum(vector& nums, int target) {
        std::unordered_mapmap; 
        for(int i = 0; i< nums.size(); i++) {
            // 遍历，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到，就把访问过的元素和下标加入到map中
            map.insert(pair(nums[i], i)); 
        }
        return {};
    }
};

本题需要我们输出索引，所以我们用map，pair(数字，索引)来表示，最后返回的也是iterator的second。还有大家做OJ的时候啊，有的题目要求必须有返回值的，读者想我们在接口里面肯定就返回了啊不可能到外面来，这个只需要在外面处理一下，写个空就好了。

454. 四数相加 II - 力扣（LeetCode）

其实几个数相加的这种问题啊，框架是差不多，但是细节实现起来就个然不同。这道题老实说一开始我也没有太好办法，你直接四个肯定超时。但是看了一下给的数据大小，n是小于200的，想了想优化下，两个数组分成一组，然后去凑。 a+b+c+d == 0， 我ab凑好了以后， 去找 0 -(a+b) 就是(c+d)。还有就是我们找到了应该＋几也是个问题，其实应该加的是key对应的value啊，千万不能加1，因为你想你a+b比如等于5，可能是1和4， 2和3， 很多种情况是不是啊，所以都要加和。

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
    unordered_mapmap1;


    for(auto e: nums1)
    {
        for(auto x: nums2)
        {
            map1[e + x]++; //我这里说一下范围for的用法，新手搞不清里面这个e是啥意思，到底是索引还是数字
        }//范围for里面的元素全部是迭代器啊，我强调一下，就是你用范围for是无法找索引的，因为他是用迭代器遍历的
    }
    int count = 0;
    for (auto e: nums3)
    {
        for(auto x: nums4)
        {
            int target = 0 - (e + x);
            if (map1.find(target) != map1.end())
            {
                count += map1[target]; 
            }
        }
    }
    return count;
    }
};

哈希表的应用和玩法还是很多的。等我啃啃书，过段时间再来讲解下一些比较难的题。感谢观看。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：哈希入门题目解决(C++)必看-创新互联
URL分享：https://www.cdcxhl.com/article34/ccchpe.html

成都网站建设公司_创新互联，为您提供动态网站、建站公司、网站营销、网站导航、响应式网站、虚拟主机

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

外贸网站建设

微信公众号知识

同城分类信息