哈希表理论基础
- 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
242. 有效的字母异位词 - 力扣（LeetCode）
解题思路
- 用一个哈希表，先记录s中字母出现次数，然后如果t中出现一样字母就-1，最后如果哈希表中存在非0值，则返回false；
- 也可以直接调用函数
方法一
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hashtable = {}
for i in s:
if i in hashtable:
hashtable[i] += 1
else:
hashtable[i] = 1
for i in t:
if i in hashtable:
hashtable[i] -= 1
for i in hashtable:
if hashtable[i] != 0:
return False
return True
方法二
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
s = Counter(s)
t = Counter(t)
return s==t
349. 两个数组的交集 - 力扣（LeetCode）
直接用set
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
- 还是没明白什么时候用数组，什么时候用set：如果范围可控、数字不大，可用数组
- "如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！" ???
202. 快乐数 - 力扣（LeetCode）
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
hashtable = {}
while True:
n_temp = 0
for ch in str(n):
n_temp += int(ch)**2
n = n_temp
if n == 1:
return True
if n in hashtable:
return False
else:
hashtable[n] = 0
- 用set、hashtable都行
1. 两数之和 - 力扣（LeetCode）
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashtable = {}
for index, value in enumerate(nums):
if target-value in hashtable:
return [hashtable[target-value], index]
else:
hashtable[value] = index
- 还可以深挖，埋个坑
