代码随想录算法训练营第5天—哈希表01 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

本文主要是介绍代码随想录算法训练营第5天—哈希表01 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈希表用于需要快速判断某个元素是否存在的场景

242.有效的字母异位词

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

考点
- 哈希表（数组）
我的思路
- 分别用两个长度为26的数组遍历记录两个输入字符串中每个字母出现的次数，这里的26分别对应26个英文字母，也就是说，我的哈希函数是0对应a一直到25对应z
- 判断两个数组是否相等，不相等则返回False，否则为True
视频讲解关键点总结
- 未看视频
- 文字版讲解的思路和我类似
我的思路的问题
- 无
代码书写问题
- 无
可执行代码

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""list_s = [0] * 26list_t = [0] * 26for a in s:list_s[ord(a) - ord('a')] += 1for b in t:list_t[ord(b) - ord('a')] += 1if list_s == list_t:return Trueelse:return False

349. 两个数组的交集

题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

考点
- 哈希表（数组/集合/字典）
我的思路
- 由于限定了输入值的范围，因此可以直接用数组来写
- 把输入值一一对应到数组的序列值上，因此创建两个1001维的数组用来记录两个输入列表出现过的值
- 记录完成后，创建一个新列表，在判断两个列表中相同位置的值均不为0时，储存结果，最终返回
视频讲解关键点总结
- 未看视频
- 文字版提供了多种思路，其中一种和上述相同
- 使用集合的话，只需要一行代码return list(set(nums1) & set(nums2))
我的思路的问题
- 无
代码书写问题
- 无
可执行代码

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""l1 = [0] * 1001l2 = [0] * 1001result = []for data in nums1:l1[data] += 1for data in nums2:l2[data] += 1for i in range(1001):if l1[i] != 0 and l2[i] != 0:result.append(i)return result

202.快乐数

题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

考点
- 哈希数据结构（数组/集合）
- 非快乐数的无限循环含义
我的思路
- 外层大循环，while true
  - 第一个小循环取出当前n的每个数位，储存到列表中
  - 第二个小循环从列表中取值进行求和
  - 接下来进行判断
    - 如果和为1，当前数为快乐数，返回true
    - 如果和在之前的大循环中出现过，说明接下来会开启无限循环，即当前数不是快乐数，因此返回false
    - 和在之前没出现过、也不为1，则储存当前的和，之后开启下一轮大循环
视频讲解关键点总结
- 未看视频
- 文字版的重点已经总结到上面的我的思路里了，因为之前我的思路对无限循环的理解不到位
我的思路的问题
- 之前没有理解好无限循环的含义，以为无限循环的情况不需要进行额外处理
代码书写问题
- 无
可执行代码

class Solution(object):def isHappy(self, n):""":type n: int:rtype: bool"""n_ = [n]while True:l = []while n:l.append(n % 10)n /= 10for data in l:n += data ** 2if n == 1:return Trueelif n in n_:return Falseelse:n_.append(n)

1. 两数之和

题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

考点
- 哈希结构（字典）
- 利用差值的思路降低时间复杂度
我的思路
- 暴力遍历所有的和值，过程中如果有和target相等的情况出现则返回
视频讲解关键点总结
- 首先，想要判断数组中是否有两个元素的和值和target相等，利用差值的思路避免嵌套循环，比如target-当前元素得到差值，如果之前遍历过的元素中有该差值，则返回，否则继续向下遍历
- 由于这里需要查询之前遍历过的元素，并且需要返回其对应的索引，因此使用字典结构，因为其查询速度快、且key-value结构与题意相符
我的思路的问题
- 没有想到利用差值降低时间复杂度
代码书写问题
- 无
可执行代码

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""dic = {}for index, data in enumerate(nums):if target - data in dic:return [dic[target - data], index]dic[data] = indexreturn []