哈希表
哈希表理论基础
哈希表(Hash Table)，是根据关键码的值而直接进行访问的数据结构。或者说：哈希表是通过建立键（key）与值（value）之间的映射，实现高效的元素查询。
如果将数组当作哈希表，那么关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
哈希表能解决什么问题
一般哈希表都是用来快速判断一个元素是否出现在集合里。使用哈希遍查询元素的时间复杂度为O(1)。哈希表的一个关键点在于设计hash function(哈希函数)。
哈希函数
哈希函数，通过hash code把元素的某些信息转换为数值，一般hash code是通过特定编码方式，可以将其他数据格式转化为不同的数值，从而为元素生成一个索引下标。
哈希碰撞（哈希冲突）
元素的信息通过hash function生成的索引下标是一样的，导致两个元素被放置在数组的同一位置，这种现象叫做哈希碰撞（哈希冲突）。通常情况下，哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。
改良哈希冲突的方法
链式地址
在原始哈希表中，链式地址将单个元素转换为链表，将所有发生冲突的键值对都存储在同一链表中。
开放寻址
开放寻址不额外引入其他的数据结构，而是通过多次探测的方式来处理哈希冲突，探测方式如下：
线性探测：采用固定步长的线性搜索进行探测，操作方式与普通哈希表有所不同。才采用线性探测处理哈希冲突的哈希表的操作方式有所不同：
- 添加元素：当插入元素的时候发现插入的位置已有元素（也就是发生了哈希冲突），则从冲突位置向后线性遍历（步长通常为1），直到找到空桶，将其插入。
- 查询元素：当发现哈希冲突，则使用相同步长向后进行线性遍历，知道找到对应元素。
线性探测的缺点：线性探测容易产生聚集效应。数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长。
平方探测：与线性探测类似，平方探测通过跳过探测次数的平方的步长，例如，1，4，9，.....
平方探测具有以下优势：
- 通过跳过探测次数的平方，试图缓解线性探测的聚集效应。
- 平方探测跳过更大的距离寻找空位置，有助于数据均匀分布。
缺点：1. 仍然存在聚集效应 2.平方探测可能不会探测整个哈希表，意味着哈希中即使存在空位置，平方探测也无法访问到它。
多次哈希：使用多个哈希函数对进行探测（探测的意思是寻找空位置）。
练习题
INFO
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
代码示例：
function isAnagram(s: string, t: string): boolean {
//字符串长度不同就不是有效的字母异位词
if (s.length !== t.length) return false;
//初始化哈希表
const hash = Array(26).fill(0) as number[];
//计算‘a’的ASCLL码
const pivot = 'a'.charCodeAt(0);
for (let i = 0, len = s.length; i < len; i++) {
//向哈希表汇总记录每个字符出现的次数
hash[s.charCodeAt(i) - pivot]++;
//对哈希表中的当前字符的位置做减法
hash[t.charCodeAt(i) - pivot]--;
}
//如果是有效的字母异位词，则最后数组的元素均为0
return hash.every((i) => i === 0);
}INFO
两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
代码示例：
function intersection(nums1: number[], nums2: number[]): number[] {
const $nums1 = new Set(nums1);
const $nums2 = new Set(nums2);
return [
...new Set(
[...$nums1].filter(i => $nums2.has(i))
)
]
}INFO
快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例：
输入：n = 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之前，将所有的计算结果存储在哈希表中，如果在哈希表中出现过计算结果，说明进入了无限循环中，那么此时需要退出循环
* @param n
* @returns
*/
function isHappy(n: number): boolean {
function calSum(val: number) {
return val
.toString()
.split('')
.reduce((prev, cur) => {
return prev + Number(cur) * Number(cur);
}, 0);
}
//初始化哈希表
let storeSet = new Set<Number>();
while (n !== 1 && !storeSet.has(n)) {
storeSet.add(n);
n = calSum(n);
}
return n === 1;
}INFO
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
代码示例：
function twoSum(nums: number[], target: number): number[] {
//初始化哈希表，哈希表的存储结构是key => 数组元素,value是元素索引
const hash = new Map();
for (let i = 0, len = nums.length; i < len; i++) {
//在遍历数组的过程中，判断 target - 当前元素nums[i]的值是否存在哈希表中
if (hash.has(target - nums[i])) {
//存在则直接返回两个元素的索引
return [i, hash.get(target - nums[i])];
} else hash.set(nums[i], i);
}
return [];
}小总结：
什么时候用哈希表？当需要在一个集合中查询元素是否出现过的时候就需要用到哈希表。
如何选择哈希表的数据结构（数组，Set,Map）？如果集合有序且集合的数据量有限时可以使用数组，当集合的数据量较大时使用set，当需要存储集合的元素的关联数据时使用Map。
哈希表day2
INFO
四数相加
给定四个包含整数的数组列表 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 。
示例：
例如: 输入: 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
代码示例：
function fourSumCount(
nums1: number[],
nums2: number[],
nums3: number[],
nums4: number[]
): number {
const hashMap = new Map();
let tempVal: number | undefined,count = 0;
for (let i of nums1) {
for (let j of nums2) {
tempVal = hashMap.get(i + j);
hashMap.set(i + j, tempVal ? tempVal + 1 : 1);
}
}
for (let k of nums3) {
for (let l of nums4) {
tempVal = hashMap.get(0 - (k + l));
if (tempVal) {
count += tempVal;
}
}
}
return count;
}INFO
赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例：
示例 1： 输入：ransomNote = "a", magazine = "b" 输出：false 示例 2： 输入：ransomNote = "aa", magazine = "ab" 输出：false 示例 3： 输入：ransomNote = "aa", magazine = "aab" 输出：true
提示：
1 <= ransomNote.length, magazine.length <= 105ransomNote和magazine由小写英文字母组成
function canConstruct(ransomNote: string, magazine: string): boolean {
const hash = new Array(26).fill(0);
const base = "a".charCodeAt(0);
for (let i = 0, length = magazine.length; i < length; i++) {
hash[magazine[i].charCodeAt(0) - base]++;
}
for (let i = 0; (length = ransomNote.length); i++) {
const index = ransomNote[i].charCodeAt(0) - base;
const ruduce = hash[index]--;
if (ruduce < 0) {
//说明 ransomNote中在 magazine 出现的字符被重复使用
return false;
}
}
return true;
}INFO
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例：
示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
代码示例：
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
let length = nums.length;
let left: number = 0,right: number = length - 1;
let resArr: number[][] = [];
for (let i = 0; i < length; i++) {
if (nums[i] > 0) {
//nums经过排序后，只要nums[i]>0, 此后的nums[i] + nums[left] + nums[right]均大于0,可以提前终止循环。
return resArr;
}
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
left = i + 1;
right = length - 1;
while (left < right) {
let total: number = nums[i] + nums[left] + nums[right];
if (total === 0) {
resArr.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (nums[right] === nums[right + 1]) {
right--;
}
while (nums[left] === nums[left - 1]) {
left++;
}
} else if (total < 0) {
left++;
} else {
right--;
}
}
}
return resArr;
}INFO
四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例：
示例 1： 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2： 输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
代码示例：
function fourSum(nums: number[], target: number): number[][] {
nums.sort((a, b) => a - b);
let first: number = 0,
second: number,
third: number,
fourth: number;
let length: number = nums.length;
let resArr: number[][] = [];
for (; first < length; first++) {
if (first > 0 && nums[first] === nums[first - 1]) {
continue;
}
for (second = first + 1; second < length; second++) {
if ((second - first) > 1 && nums[second] === nums[second - 1]) {
continue;
}
third = second + 1;
fourth = length - 1;
while (third < fourth) {
let total: number = nums[first] + nums[second] + nums[third] + nums[fourth];
if (total === target) {
resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);
third++;
fourth--;
while (nums[third] === nums[third - 1]) third++;
while (nums[fourth] === nums[fourth + 1]) fourth--;
} else if (total < target) {
third++;
} else {
fourth--;
}
}
}
}
return resArr;
};