哈希专题总结(上)

算法训练营第10天，中间因为身体原因落了两天进度，有点赶不上，但也不能着急，该学的还是得先掌握好才可以。(-_-|||)

1.力扣242

这是我第一次利用哈希表做题，学校教的仅仅是理论知识，只知哈希不知道怎么用，现在才理解它的妙用。

本题用数组作为一个哈希表，首先存储数据，之后用待测试数据进行删除操作，如果表中的数据为0，说明数据都被取走(即符合要求），反之，若是正数或负数说明两组字符串中一定其中一方多或是少了字符，很巧妙的思想。关键部分在这里：

挺简单的一道题。

2.力扣349

紧承242的数组哈希，接下来是set的应用，本题主要使用unorder_set，其底层也是哈希，哈希一般用于快速判断某个数是否在集合中 ，这道题要求交集并且元素唯一，很自然的就能够想到利用哈希来解决问题。

二者区别在于，数组面对分散且跨度大的数据 非常浪费空间，它需要申请一系列连续的内存地址，而unordered_set则解决了这个问题，虽然这道题限制了数量可以用数组哈希，但母庸置疑，unordered_set是主要考察的知识。

在做题过程中我并不是很理解for(:)的用法，以及为何find函数‘’！=‘’就能够判断是否查找成功（不应该是==吗），通过翻阅primer和查找博客我找到了如下的知识：

现在贴上源代码：

现在就很容易理解为什么这里会这样做了，它利用了c++11的新特性，也算是又学到了一点东西吧(笑)。

3.不快乐的快乐数

**** 每每遇到这种类似数学想法的题目我都会想：他们到底脑子里都在想些什么怪东西！

**** 第一次读题似懂非懂，知道要求出各位数的平方后便束手无策，看了卡哥题解才发现无限循环 是关键，将所有求和的值存储到哈希表中，一旦有循环的可能便及时终止，反之持续到和为1。当然，因为数量较大，依然使用unordered_set。

求位数的操作算是绕了点脑弯，不理解的话举个例子也能得出，首先是个位，之后继续向上：

理解思路后也不是那么不快乐了呢！

4.新手劝退第一题再战！

啊，两数之和，一开始就把我拿捏的死死的，用了暴力解法看不懂哈希的我，今天打败你了！

这道题不仅要知道元素是否遍历过，还得知道这个元素对应的下标，综合思考，map是最合适的选择。

map是另一种数据结构，我理解为python中的键值对，因为这道题也涉及判断原宿是否在数据中，所以利用哈希的map比较合适，unordered_map又是新的一个知识点。

首先是定义：std::unordered_map <int,int> map;类似set的定义方式，只不过键值对需要两个初始化。

接下来是思考如何继续。我们可以在遍历一个元素时把它存入哈希表中，在遍历下一个元素时判断现在哈希表中的数和现在正在遍历的数是否符合条件，我们要确定键是谁，值是谁 ，这取决于题目要求我们返回什么东西，在这里遍历的元素是键，值是下标。

主要部分在这：

OK，到 iter->second 我又不理解了，这是什么登西，通过primer我又看到了这些：（primer真是圣经啊！！）

下面又给出了更明白的例子:

现在一切都清楚多了。

我发现我慢慢有了思路，写代码时知道哪个要在这里，哈希明显感觉要比之前写的顺利多，虽然定义这里还不是很熟，但相比以前，我确实好的太多了。

加油！