**哈希表，也叫散列表，是可以通过关键字key访问映射表来得到value的地址，从而可以直接通过key获取其对应的value的值的数据结构，这个映射表也叫哈希函数，存放value的数组叫做哈希表。**

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

解决哈希冲突的方法：

1. 链地址法：对Key通过哈希之后落在同一个地址上的值，做一个链表来进行存储同一个key对应的不同的值。

2. 开放地址法：如果出现一个key2进行hash(key)后映射的位置与key1进行hash(key)后映射的位置一致（即发生了哈希冲突），那么从该位置往下寻找到第一个空位时将key2的数据放入。而从该位置往下寻找空闲位置的过程又称为探测。

* [有效的字母异位词](有效的字母异位词.md)

* [两个数组的交集](两个数组的交集.md)

* [快乐数](快乐数.md)

* [两数之和](两数之和.md)

* [四数相加II](四数相加II.md)

* [赎金信](赎金信.md)

给定两个数组，编写一个函数来计算它们的交集。

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[9,4]

* 将列表转换为集合，集合的特性是去重，查找时间复杂度O(1)

* 遍历其中一个集合，判断元素在另一个集合中是否出现

* 时间复杂度O(m+n):其中m和n分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要O(m+n)的时间，遍历较小的集合并判断元素是否在另一个集合中需要O(min(m,n))的时间，因此总时间复杂度是O(m+n)。

* 空间复杂度:O(m+n)

def intersection(nums1, nums2):

set1 = set(nums1)

set2 = set(nums2)

if len(set1) < len(set2):

# 遍历短的提高效率

return [item for item in set1 if item in set2]

return [item for item in set2 if item in set1]

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

nums = [3,3],target=6

[0,1]

用字典存储每个元素及其对应的索引。时间复杂度O(n),空间复杂度O(n)

* 从前向后依次遍历数组中的元素。

* 计算差值，如果差值不存在字典中，则保存当前遍历的元素到字典中。

* 如果差值存在字典中，返回差值的索引与当前元素的索引。

def twoSum(nums, target):

hash_table = {}

for index, item in enumerate(nums):

other = target - item

if other in hash_table:

return [index, hash_table[other]]

hash_table[item] = index

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

输入:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

输出:

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

* 与[两数之和](两数之和.md)有点相似,将四个数组分成两组，AB一组，CD一组

* 对于A和B，使用二重循环对它们进行遍历，得到所有A[i]+B[j]的值并存入哈希映射中。每个键表示一种A[i]+B[j]，对应的值为 A[i]+B[j]出现的次数。

* 对于C和D，同样使用二重循环对它们进行遍历。当遍历到C[k]+D[l] 时，如果-(C[k]+D[l])出现在哈希映射中，那么将 -(C[k]+D[l])对应的值累加进答案中。

* 时间复杂度O(n^2), 空间复杂度O(n^2)

def fourSumCount(A, B, C, D):

# 记录AB两个数组元素两两相加之和及其次数

hash_1 = dict()

for index_1, item_1 in enumerate(A):

for index_2, item_2 in enumerate(B):

sum_ = item_1 + item_2

hash_1[sum_] = hash_1.get(sum_, 0) + 1

ans = 0

for index_1, item_1 in enumerate(C):

for index_2, item_2 in enumerate(D):

sum_ = item_1 + item_2

if 0-sum_ in hash_1:

ans += hash_1[0-sum_]

return ans

编写一个算法来判断一个数 n 是不是快乐数。

* 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

* 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

* 如果 可以变为 1，那么这个数就是快乐数。

输入：19

输出：true

解释：

1 + 81 = 82

64 + 4 = 68

36 + 64 = 100

1 + 0 + 0 = 1

* 可能最终会得到1

* 可能最终会无限循环

* 会不会无限增大

* 如果是一位数，最大为9，平方和最大是81

* 如果是两位数，最大为99，平方和最大为162

* 如果是三位数，最大为999，平方和最大为243

* 如果是四位数，最大为9999，平方和最大为324

**所以对于三位数的整数，它的下一个数字（每个位置数字的平方和）不会大于243，对于四位和四位以上的整数，每次计算都会减小，最终变为三位数的整数，所以结果不会无限增大，算法可能会在243以下的所有数字上循环，然后回到它已经到过的一个循环或者回到1。**

**判断元素是否重复出现就要考虑使用哈希表。**

* 逐个计算下一个数字，并将结果保存在哈希表中

* 如果结果出现1，返回True

* 如果出现重复的结果，说明出现循环，返回False

class Solution:

def isHappy(self, n: int) -> bool:

def get_next(n):

sum = 0

while n > 0:

sum += (n % 10) ** 2

n = n // 10

return sum

hash_table = dict()

while n not in hash_table:

if n == 1:

return True

hash_table[n] = None

n = get_next(n)

return False

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

输入: s = "anagram", t = "nagaram"

输出: true

输入: s = "rat", t = "car"

输出: false

* 如果两个字符串长度不相等直接返回False

* 利用两个字典统计每个字符串中字符出现的次数

* 如果两个字典相等，返回True

def isAnagram(s, t):

if len(s) != len(t):

return False

if s == t:

return True

hash_s = {}

hash_t = {}

for i in range(len(s)):

hash_s[s[i]] = hash_s.get(s[i], 0) + 1

hash_t[t[i]] = hash_t.get(t[i], 0) + 1

return hash_t == hash_s

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

输入：ransomNote = "a", magazine = "b"

输出：false

输入：ransomNote = "aa", magazine = "aab"

输出：true

* 根据题目分析，ransom中字符出现的个数必须小于等于magazine中字符出现的次数

* 分别统计ransom，magazine中字符出现的次数

* 比较ransom，magazine每个字符出现的次数

def canConstruct(ransomNote, magazine):

hash_1 = dict()

hash_2 = dict()

for char in ransomNote:

hash_1[char] = hash_1.get(char, 0) + 1

for char in magazine:

hash_2[char] = hash_2.get(char, 0) + 1

for char, times in hash_1.items():

if hash_2.get(char, 0) < times:

return False

return True