代码随想录 Day6 | 哈希表-part01（ 242.有效的字母异位词、349. 两个数组的交集 、202. 快乐数、1. 两数之和 ）

今日总结数组、集合、字典和哈希表题目242. 有效的字母异位词题目链接题目题解第一想法用两个[0]*26的数组模拟哈希表自己实现class Solution: def isAnagram(self, s: str, t: str) - bool: arr [0]* 26 arr2 [0]* 26 for c in s: arr[ord(c)-ord(a)] 1 for c in t: arr2[ord(c)-ord(a)] 1 print(arr) print(arr2) for i in range(26): if arr[i] ! arr2[i]: return False return True时间复杂度: O(n)空间复杂度: O(1)学习题解可以用字典或collections.Counter统计直接比较两个 Counter 是否相等。from collections import Counter优化只用一个数组遍历 s 时计数加一遍历 t 时减一最后检查数组是否全为零。class Solution: def isAnagram(self, s: str, t: str) - bool: if len(s) ! len(t): return False arr [0]*26 for c in s: arr[ord(c)-ord(a)] 1 for c in t: arr[ord(c)-ord(a)] - 1 return all(x 0 for x in arr)349. 两个数组的交集题目链接题目题解第一想法2个集合。用集合存储一个数组的元素遍历另一个数组时判断是否在集合中同时用另一个集合去重。自己实现class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: set1 set() res set() for a in nums1: if a not in set1: set1.add(a) for b in nums2: if b in set1 and b not in res: res.add(b) # 注意返回list return list(res)易错点一开始忘记返回list返回set报错时间复杂度: O(nm)空间复杂度: O(n)学习题解由于题目限制了0 nums1[i], nums2[i] 1000也可以使用长度为 1001 的数组模拟哈希表。更简洁的写法return list(set(nums1) set(nums2))202. 快乐数题目链接题目题解第一想法不断计算各位平方和直到结果为 1 或进入循环。需要记录出现过的数字来判断循环。自己实现错解1:class Solution: def isHappy(self, n: int) - bool: # 如果用字符串需要不断转换用数字需要计算 num n while num: sum_sq 0 while num: sum_sq (num%10) * (num%10) num num//10 if sum_sq 1: return True elif num sum_sq: break else: num sum_sq return False错因while num:在num变为 0 时会退出此时num已被修改导致比较逻辑错误。修正可以用集合存储出现过的数字判断重复class Solution: def isHappy(self, n: int) - bool: num n seen set() # 把判断放到循环入口用集合判断重复 while num!1 and num not in seen: sum_sq 0 seen.add(num) while num: sum_sq (num%10) * (num%10) num num//10 num sum_sq return num 1时间复杂度O(log n)实际上与数值的位数有关空间复杂度O(log n)存储出现过的数字学习题解也可以用快慢指针龟兔赛跑检测循环快指针每次计算两次平方和慢指针一次若快指针先到 1 则快乐若快慢指针相遇且不为 1 则说明陷入非 1 循环。1. 两数之和题目链接题目题解第一想法用哈希表存储target-nums[index]index然后第二次遍历查找匹配。自己实现class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: s {} for i in range(len(nums)): s[target-nums[i]] i for i in range(len(nums)): if nums[i] in s and i ! s[nums[i]]: return [i,s[nums[i]]]时间复杂度O(n)空间复杂度O(n)学习题解优化只需一次遍历边存边查。对于当前元素nums[i]检查target - nums[i]是否已在哈希表中若在则直接返回否则将当前元素及其下标存入哈希表。class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []也可用排序 双指针但需要记录原始下标实现稍复杂。感觉重点是区分index和nums[index]今日收获哈希表基础数组、集合、字典都可以作为哈希表根据数据范围选择合适的实现。字母异位词可以用一个数组做加减法最后检查是否全零。交集利用集合的交集运算简化代码。快乐数用集合记录历史值检测循环或用快慢指针。两数之和哈希表一次遍历的经典应用边存边查。学习时间昨天忘记打卡今日11:20-12:30约1h注意效率模板数组作为哈希表字母计数arr [0] * 26 for c in s: arr[ord(c) - ord(a)] 1集合去重s set() s.add(x) if x in s: ...哈希表字典一次遍历pythonseen {} for i, num in enumerate(nums): if target - num in seen: return [seen[target - num], i] seen[num] i快乐数循环检测集合pythonseen set() while n ! 1 and n not in seen: seen.add(n) n sum(int(d)**2 for d in str(n)) return n 1易错点242题注意数组下标计算ord(c)-ord(a)确保不越界。349题返回类型如果是list不能直接返回set。202题循环条件容易写错确保进入循环前已存储当前数避免死循环。1题注意返回的下标顺序以及避免使用同一个元素两次通过先检查后存值解决。