代码随想录算法训练营第六天 | 哈希表 part01

哈希表（Hash Table）是一键值对（key-value）的高效数据结构。
哈希表的核心特性：平均时间复杂度 O ( 1 ) O(1) O(1)的增、删、查操作。
常见的哈希结构：

• 纯哈希表（键值对哈希）：标准的哈希实现，键唯一、值可任意。支持[增/删/改/查]操作。语言实现：Python dict、Java HashMap/Hashtable、JavaScript Map（推荐）/Object（简易版）、C++ unordered_map、Go map
• 哈希集合：只存键、不存值的哈希表，利用键的唯一性实现去重，支持[增/删/判]操作。语言实现：Python set、Java HashSet、JavaScript Set、C++ unordered_set、Go 无内置 Set（可通过 map[T]struct{} 模拟，空结构体不占内存）。

当我们遇到了要快速判断一个元素是否出现在集合里的时候，就要考虑哈希法。哈希法牺牲了空间来换取时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

题目一leetcode 242.有效的字母异位词
字母异位词的核心判断条件：

• 两个字符串长度必须相等（剪枝：长度不同之间return False）
• 两个字符串中每个字符出现的频率完全一致
  思路一：可以对两个字符串进行分别进行排序，然后再比较两个字符串是否相等，时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
  思路二：实际上，判断字符串t是否是s的字母异位词，只需要判断相同字母出现的次数是否相同即可。由于字符串只包含26个小写字母，我们可以用一个长度为26的数组记录s中字母出现的频次，然后再遍历t去抵消对应频次，最终若所有字符频率都为0，就return True。

defisAnagram(self, s:str, t:str)->bool:iflen(s)!=len(t):returnFalse record =[0]*26for char in s: record[ord(char)-ord('a')]+=1for char in t: record[ord(char)-ord('a')]-=1if record[ord(char)-ord('a')]<0:returnFalsereturnTrue

进阶问题要求支持Unicode字符（比如中文、特殊符号、大写字母等），此时一个固定长度的数组无法满足，需要用通用哈希表实现，比如python中的dict。

defisAnagram(s:str, t:str)->bool:iflen(s)!=len(t):returnFalse freq ={}for c in s: freq[c]= freq.get(c,0)+1for c in t:if freq.get(c,0)==0:returnFalse freq[c]-=1returnTrue

题目二leetcode 349.两个数组的交集
主要的难点在于输出结果中的每一个元素一定是唯一的，需要去重。

如果题目没有限制数值的大小，就无法使用数组来做哈希表。另外，如果哈希值比较少，特别分散、跨度非常大，使用数组就造成空间的极大浪费。

defintersection(self, nums1: List[int], nums2: List[int])-> List[int]: record =dict() intersection =[]for num in nums1: record[num]=0for num in nums2:if num in record: record[num]=1for key, value in record.items():if value ==1: intersection.append(key)return intersection defintersection(self, nums1: List[int], nums2: List[int])-> List[int]: st =set(nums1) ans =[]for x in nums2:if x in st: st.remove(x) ans.append(x)return ans 

题目三leetcode.202 快乐数
1.根据题目可以得出主要有两种情况，一种是找到sum为1，一种是sum开始循环出现。所以这道题目使用哈希法，记录每次sum的值，如果遇到重复值则return False，否则一直计算，知道sum为1，return True。

defisHappy(self, n:int)->bool: result =set()while n !=1:sum=0 nums =[int(char)for char instr(n)]for num in nums:sum+= num**2ifsumin result:returnFalse result.add(sum) n =sumreturnTrue

2.也可以使用快慢指针来做，原理是检测该数据链是否成环。如果n不是快乐数，那么快指针总有一个时刻会追上慢指针。

defisHappy(self, n:int)->bool:defget_next(number): total_sum =0while number >0: number, digit =divmod(number,10) total_sum += digit**2return total_sum slow_runner = n fast_runner = get_next(n)while fast_runner !=1and slow_runner != fast_runner: slow_runner = get_next(slow_runner) fast_runner = get_next(get_next(fast_runner))return fast_runner ==1

题目四leetcode 1.两数之和
暴力解法进行遍历，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。很自然想到可以用哈希表记录每一个x，然后在遍历时查询哈希表中是否存在target - x，时间复杂度降为 O ( n ) O(n) O(n)。注意，这里元素是key，value是数组元素对应的下标。

# 暴力解法deftwoSum(self, nums, target):for i inrange(len(nums)):for j inrange(i +1,len(nums)):if((nums[i]+ nums[j])== target):return[i,j]returnNone# hashtabledeftwoSum(self, nums: List[int], target:int)-> List[int]: hashtable =dict()for i, num inenumerate(nums):if target - num in hashtable:return[hashtable[target-num], i] hashtable[num]= i returnNone