哈希表
哈希表：用来快速判断一个元素是否出现在集合里；O（1）；
哈希碰撞：比如小王和小李都映射到索引下表1的位置，有2中解决办法（拉链法和线性探测法）；
拉链发：通过索引找到，其实拉链发就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间；
线性探测法：一定要保证tablesize大于datasize。我们需要哈希表中的空位来解决碰撞问题；例如冲突的位置，放了小李，那么就向下找一个空位置放置小王的信息。
常见的三种哈希结构：数组，set（数组），map（映射）；
当我们遇到了要快速判断一个元素是否出现在集合里的时候，就要考虑用哈希表；（哈希表是通过牺牲了空间换取了时间）
242. 有效的字母异位词 - 力扣（LeetCode）
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# 一共26个字母，全部包含
record = [0] * 26
for i in s:
# 计算对应字母的位置，存在即+1
# 无需记住字符a的ascii,只要计算方式相同，就代表同一个字母
record[ord(i) - ord('a')] += 1
# 在对应的record中，若存在位置相同的，即-1；
for j in t:
record[ord(j) - ord('a')] -= 1
# 遍历数组，是否存在非0元素，若存在，则返回False;
for i in range(len(record)):
if record[i] != 0:
return False
return True
if __name__ == '__main__':
s = "rat"
t = "car"
res = Solution().isAnagram(s, t)
print(res)349. 两个数组的交集 - 力扣（LeetCode）
思路：1、输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的；
2、同时可以不考虑输出结果的顺序；
方法1、偷懒的方法，使用set函数（自己想的）
from typing import List
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res1 = set(nums1)
res2 = set(nums2)
res = []
for i in res1:
if i in res2:
res.append(i)
return res
if __name__ == '__main__':
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
res = Solution().intersection(nums1, nums2)
print(res)方法2、使用数组来做哈希的题目，是因为题目都限制了数值的大小；
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的，不要小瞧 这个耗时，在数据量大的情况，差距是很明显的；
from typing import List
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 力扣改了题目描述和后台测试数据，增添了数值范围，数组都是 1000以内的；
count1 = [0] * 1001
count2 = [0] * 1001
res = []
# nums1出现的数在count1进行计数，出现多少个
for i in range(len(nums1)):
count1[nums1[i]] += 1
# # nums2出现的数在count2进行计数，出现多少个
for j in range(len(nums2)):
count2[nums2[j]] += 1
# 当count1和count2中相同的位置的数据相乘大于0，代表两个数组都有该值，即该值为交集；
for m in range(1001):
if count1[m] * count2[m] > 0:
res.append(m)
return res
if __name__ == '__main__':
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
res = Solution().intersection(nums1, nums2)
print(res)202. 快乐数 - 力扣（LeetCode）
有很多的方法完成这个题，我选了数组法，比较好理解（自我感觉）；
class Solution:
def isHappy(self, n: int) -> bool:
result = []
# 当n没有在result中出现，代表不是无线循环，若出现n，则代表不会出现1的情况；
while n not in result:
result.append(n)
new_num = 0
n_str = str(n)
# 计算每个值每个位数的平方和
for i in n_str:
new_num += int(i)**2
if new_num == 1:
return True
else:
n = new_num
return False
if __name__ == '__main__':
n = 1953445
res = Solution().isHappy(n)
print(res)1. 两数之和 - 力扣（LeetCode）
1、暴力法（双for循环）(O(N^2))（自己想的）
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
if __name__ == '__main__':
nums = [3, 2, 4]
target = 6
res = Solution().twoSum(nums, target)
print(res)2、暴力法使用双for循环，联想到使用双指针的方式进行解答：
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 对数据进行排序，形成升序的新数组
nums_sorted = sorted(nums)
# 定义双指针（前后个一个指针）
left = 0
right = len(nums_sorted) - 1
# 这里没有=，因为要两个数，不会出现同一个索引数据出现2次的情况，只会出现在不同索引位置出现相同的数据；
while left < right:
tmp = nums_sorted[left] + nums_sorted[right]
if tmp == target:
# 需要查找目标值索引（因为一开始进行了排序，索引乱掉）
left_index = nums.index(nums_sorted[left])
right_index = nums.index(nums_sorted[right])
# 会出现两个相同的数值索引到同一个位置，数值没有索引到后面的位置
if left_index == right_index:
# 在出现第一个索引之的后面开始重新索引
# a = nums[left_index + 1:].index(nums_sorted[right])
# b = nums[left_index + 1:].index(nums_sorted[right]) + left_index
right_index = nums[left_index + 1:].index(nums_sorted[right]) + left_index + 1
return [left_index, right_index]
elif tmp < target:
left += 1
else:
right -= 1
if __name__ == '__main__':
nums = [1, 3, 3]
target = 6
res = Solution().twoSum(nums, target)
print(res)