算法刷题-哈希表的总结

什么时候用数组、什么时候用map呢？

经常会混淆。 混淆1：例如有时候题目可能要求在一大堆元素里找目标元素，要求不能利用用过的字母，这就会让我想到只包含一个键值的set或者是map，但实际上忽略了字母（限定大小写的情况下）是只有26个字母的情况，那么这个时候限定了范围大小就可以用一个vector容器或者是直接int a[26]，这样直接利用ASCII码的原理记录什么字母出现了几次，用一次减一个就OK了 例如用来判断有效异位单词和赎金信这样的题。

混淆2：同样是不让使用重复的元素，但这个元素是数字的情况下，例如是求几个数之和这样的情况，仍然是这几种情况，利用哈希表[target-某key]是否存在，前提也是要么记录了一些和出现的次数，那么如果有就可以返回在这一种相等的情况下有几次，或者需要索引的情况下，就用map这样的有键值对的，值就是存储对应元素的下标，找到是否存在之后，就可以获取她的下标二零

当然，有的地方用哈希表好像很合适，但实际上要设计去重之类的，像三数之和这样的题目，用双指针法更加合适。

混淆1 对应的题-有效异位单词、赎金信

赎金信题目： 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以，返回 true ；否则返回 false。magazine 中的每个字符只能在 ransomNote 中使用一次。 有效异位单词： 就判断一个单词是不是另一个单词的字母重组的就行。

要点

这里当然就是记录出现的次数++，然后再另一个里面出现的次数–，如果出现了正值或者负值的情况，根据不同的题目判断。

混淆2 对应的题–两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

示例 1： 输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 2： 输入：nums = [3,3], target = 6 输出：[0,1]

要点

直接在一层遍历里完成两项任务，一个是查找哈希表是否存在[target-当前value]的键，一个是如果没找到就添加当前value。一个for完成两件事

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map<int,int> nums_map; for (int i = 0; i < nums.size(); i++) { auto it = nums_map.find(target-nums[i]); if ( it != nums_map.end()) { return { it->second, i}; } nums_map.insert(pair<int,int> (nums[i], i)); } return {}; } }; 混淆2-四数相加||

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足： 0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

要点

这个就是要求返回有多少个，那么键值对应的值就应该填入出现的次数。那么在本题里面，出现的次数就指的是前两个数组的不同下标元素相加的和出现的次数了。

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int count = 0; unordered_map<int, int> GroupAandB; for (int a : nums1) { for (int b : nums2) { GroupAandB[a + b]++; } } for (int c : nums3) { for (int d : nums4) { if (GroupAandB.find(0-(c + d)) != GroupAandB.end()) { count += GroupAandB[0 - (c + d)]; //加上键值 } } } return count; } };