一般哈希表都是用来快速判断一个元素是否出现在集合里
常见的哈希结构：array、set、map
问题：有效的字母异位词 问题描述：
1 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例：
1 2 输入: s = "anagram", t = "nagaram" 输出: true
解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var isAnagram = function (s, t ){ if (s.length !== t.length ) return false ; const resSet = new Array (26 ).fill (0 ); const base = "a" .charCodeAt (0 ); for (const i of s) resSet[i.charCodeAt (0 )-base]++; for (const i of t) resSet[i.charCodeAt ()-base]--; for (let i=0 ;i<26 ;i++) if (resSet[i]!=0 ) return false ; return true ; }
问题：两个数组的交集 问题描述：
1 2 给定两个数组，编写一个函数来计算它们的交集。其实就是找两个数组的共同元素，结果需要去重。 说明:输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。所以可以考虑先去重。
示例：
解法图示：
解法：
1 2 3 4 5 6 7 8 9 var intersection = function (nums1, nums2 ){ const set1 = new Set (nums1); let res = []; for (let v of nums2) if (set1.has (v)) res.push (v); res = [...new Set (res)]; return res; }
问题：快乐数 问题描述：判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
1 2 3 4 5 6 7 输入：19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
解题重点：
1 题目中重点强调无限循环，所以在求和过程中，sum有可能会重复出现。
解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var getSum = function (n ){ let sum = 0 ; while (n){ sum += (n%10 )**2 ; n = Math .floor (n/10 ); } return sum; } var isHappy = function (n ){ let set = new Set (); while (n!==1 &&!set.has (n)){ set.add (n); n = getSum (n); } return n===1 ; }
问题：两数之和 问题描述：
1 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
1 2 3 输入：nums = [2, 7, 11, 15], target = 9 输出：[0, 1] 解释：nums[0] + nums[1] = 2 + 7 = 9
解法：
1 2 3 4 5 6 7 8 9 var twoSum = function (nums, target ){ let hash = {}; for (let i=0 ;i<nums.length ;i++){ if (hash[target-nums[i]] !== undefined ) return [i, hash[target-nums[i]]]; hash[nums[i]] = i; } return []; }
问题：四数相加II 问题描述：
1 2 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。 也就是元素可以重复。
示例：
1 2 3 4 5 6 7 8 9 10 输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
解题步骤（两两相加）：
1 2 3 4 5 1. 首先定义一个unordered_map，key放a和b两数之和，value放a和b两数之和出现的次数。 2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。 3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。 4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。 5. 最后返回统计值 count 就可以了
解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var fourSumCount = funciton (nums1, nums2, nums3, nums4 ){ const twoSumMap = new Map (); let count = 0 ; for (const n1 of nums1){ for (const n2 of nums2){ const sum = n1 + n2; twoSumMap.set (sum, (twoSumMap.get (sum)||0 )+1 ); } } for (const n3 of nums3){ for (const n4 of nums4){ const sum = n3 + n4; count += (twoSumMap.get (-sum)||0 ) } } return count; }
问题：赎金信（与有效的字母异位词类似） 问题描述：
1 2 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var canConstruct = function (ransomNote, magazine ){ const strArr = new Array (26 ).fill (0 ); const base = 'a' .charCodeAt (); for (const s of magazine){ strArr[s.charCodeAt ()-base]++; } for (const s of ransomNote){ const index = s.charCodeAt ()-base; if (!strArr[index]) return false ; strArr[index]--; } return true ; }
问题：三数之和 问题描述：
1 2 3 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意： 答案中不可以包含重复的三元组。
示例：
1 2 3 输入：nums = [-1, 0, 1, 2, -1, -4] 输出：[ [-1, 0, 1], [-1, -1, 2] ] //与两数相加的例子不同，此处只要返回数字，而两数相加需要返回索引，所以两数相加不适合用双指针
解法图示（双指针）：
细节 - 需要去重 ，不能有重复的三元组，但是三元组内的元素是可以重复的：
1 2 3 4 5 6 7 8 //应该的写法 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //不应该这么操作：会把三元组中出现重复元素的情况直接pass掉 if (nums[i] == nums[i + 1]) { // 去重操作 continue; }
解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 var threeSum = function (nums ){ const res = [], len = nums.length ; nums.sort ((a, b )=> a-b); for (let i=0 ;i<len;i++){ let left = i+1 , right=len-1 ,iNum = nums[i]; if (iNum>0 ) return res; if (iNum===nums[i-1 ]) continue ; while (left<right){ let lNum = nums[left], rNum = nums[right], threeSum = nums[i]+lNum+rNum; if (threeSum<0 ) left++; else if (threeSum>0 ) right--; else { res.push ([iNum, lNum, rNum]); while (left<right&&nums[left]==nums[left+1 ]) ++left; while (left<right&&nums[right]==nums[right-1 ]) --right; } left++; right--; } } return res; }
问题：四数之和 问题描述
1 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。答案中不可以包含重复的四元组。
示例：
1 2 输入：nums = [1, 0, -1, 0, -2, 2]，target = 0 输出：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
解法（双指针）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 var fourSum = function (nums, target ){ const len = nums.length ; if (len<4 ) return []; nums.sort ((a,b )=> a-b); const res = []; for (let i=0 ;i<len-3 ;i++){ if (i>0 &&nums[i]===nums[i-1 ]) continue ; for (let j=i+1 ;j<len-2 ;j++){ if (j>0 &&nums[j]===nums[j-1 ]) continue ; let left=j+1 ,right=len-1 ; while (left<right){ const sum=nums[i]+nums[j]+nums[left]+nums[right]; if (sum<target) left++; else if (sum>target) right--; else { res.push ([nums[i],nums[j],nums[left],nums[right]]); while (left<right&&nums[left]===nums[left+1 ]) ++left; while (left<right&&nums[right]===nums[right-1 ]) --right; } } } } return res; }
