哈希表

哈希表可以根据键在O(1)时间内进行访问。
哈希表实际上可以看成是一个数组，但是可以通过哈希函数计算出数组下标，直接访问。

常用的有集合set()，字典dict()。

有效的字母异位词 242.

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

1. 使用数组

class Solution:def isAnagram(self, s: str, t: str) -> bool:record = [0] * 26for i in s:#并不需要记住字符a的ASCII，只要求出一个相对数值就可以了record[ord(i) - ord("a")] += 1for i in t:record[ord(i) - ord("a")] -= 1return  all(x == False for x in record)

2. 使用字典

class Solution:def isAnagram(self, s: str, t: str) -> bool:from collections import defaultdicts_dict = defaultdict(int)t_dict = defaultdict(int)for x in s:s_dict[x] += 1for x in t:t_dict[x] += 1return s_dict == t_dict

Python还提供了一个默认的计数器Counter，效果和上面一样。

class Solution(object):def isAnagram(self, s: str, t: str) -> bool:from collections import Counterreturn Counter(s) == Counter(t)

两个数组的交集 349.

#集合
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。
Python 的set实现了集合运算，直接转换成集合然后求交。

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:set_1 = set(nums1)set_2 = set(nums2)return  list(set_1 & set_2)

快乐数 202.

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

使用集合来判断n有没有出现过。

class Solution:def isHappy(self, n: int) -> bool:def get_sum(num):s = 0while num:     s +=  (num % 10)** 2num =  num // 10return svisited = set()while n != 1 and  not n in visited:visited.add(n)n = get_sum(n)return  n == 1

除了正常的取余获得num各位数字，还可以用字符串：

n = sum(int(i) ** 2 for i in str(n))

两数之和 1.

#字典
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
容易想到用暴力循环来两两匹配，时间复杂度为O(N^2)。但是学完字典后，可以想到用字典存储出现过的数字及下标。 遍历过程中可以查看字典中是否有能组成target的数。时间复杂度为O(N)。
（也可以用集合存储数字，但是还需要找一次下标）

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:d = dict()for i,n in enumerate(nums):if target-n in d:return i, d[target-n]else:d[n] = i

四数相加II 454.

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

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

两数相加的扩展版。
从四个数组中各取一个数，和为0。
容易想到将四数相加变成两数相加。这样就将4重循环变成2重循环。
nums1 + nums2 = -(nums3 + nums4)

class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:d = defaultdict(int)for i in nums1:for j in nums2:d[i+j]  += 1count  = 0 for k in nums3:for l in nums4:count += d[-(k+l)]return count

赎金信 383.

#字典
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

和 有效的字母异位词有点像，但是这里只要magazine中字符数量大于ransomNote。

class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:d_ransomNote = Counter(ransomNote)d_magazine = Counter(magazine)for k,v in d_ransomNote.items():if k not in d_magazine or d_magazine[k] < v:return Falsereturn True

三数之和 15.

#字典 #双指针
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。
可以用字典做，两重循环确定num[i]和nums[j]，然后用字典确定是否有nums[k] == -(nums[i]+ nums[j])。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:d = defaultdict(list)for i,n in enumerate(nums):d[n].append(i)res = set()for i in range(len(nums)):for j in range(i+1, len(nums)):if  -(nums[i] + nums[j]) in d and d[-(nums[i] + nums[j])] != [i] \and d[-(nums[i] + nums[j])] != [j]  and d[-(nums[i] + nums[j])] != [i,j]:res.add(tuple(sorted([nums[i], nums[j],-(nums[i] + nums[j]) ])))return [list(t) for t in res]

双指针：
需要先对nums排序。
固定i后，用指针left和right找剩余的两个数。
（这里我去重直接用了set，没有像网站那样额外判断。）

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()res = set()for i in range(len(nums)):if nums[i] > 0:breakif i > 0 and nums[i] == nums[i-1]:continueleft = i+1right = len(nums) - 1while right > left:s = nums[i] + nums[left] + nums[right]if s < 0:left += 1elif s > 0:right -= 1else:res.add((nums[i], nums[left], nums[right]))right -= 1left += 1return  [list(t)  for t in res]

四数之和 18.

#双指针
在三数之和的基础上再套一层for循环。

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:   nums.sort()res  = set()for i in range(len(nums)):for j in range(i+1, len(nums)):left = j+1right = len(nums) - 1while left < right:s = nums[i]+nums[j] + nums[left] + nums[right]if s < target:left += 1elif s > target:right -= 1else:res.add((nums[i],nums[j] , nums[left] , nums[right]))left += 1right -= 1return  [list(t)  for t in res]

哈希表小结

哈西表常用来判断元素是否出现过，统计出现次数，去重。
本章题目大多数和数组相关，用到了对数组排序、双指针的方法。