哈希表Python首刷和基础学习（力扣242. 有效的字母异位词）

（1）哈希表基础：

解决问题： 一般哈希表都是用来快速判断一个元素是否出现集合里。

常见结构： 数组， set （集合）， map(映射)

大致总结：
遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

（2）力扣242. 有效的字母异位词：

题目：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

思路：

（1）用数组表示每个字符出现的次数
（2）用英文字母之间的ASCII值来做数组的下标，因为英文26字母ASCII值都是连续的，只要两个字母之间的ASCII值相减即可表示当前字母的下标
（3）先遍历s字符串，统计每个字母出现次数（+=1）
（4）再遍历t字符串，对相应的字母次数减去（-= 1）
（5）最后遍历数组，如果有！=0的就不是字母异位词，返回False。否则返回True

Python代码：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0]*26  
        for i in s:                             #遍历s字符串，对应相加
            record[ord(i)-ord('a')] += 1     #ord是返回字符相应的ASCII
        for j in t:                             #遍历t字符串，对应相减
            record[ord(j)-ord('a')] -= 1
        for i in record:          #遍历数组，有不为0说明不是字母异位词
            if i != 0:
                return False
        return True

（2）力扣349. 两个数组的交集：

题目：
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路：

这个题比较简单
（1）用数组hash建立哈希表
（2）记录第一个数组每个数是否出现过，出现记为1
（3）然后遍历另外一个数组，判断hash是否为 1 ，出现过就将该数记录到结果数组中（res）
（4）然后将对应的hash变为0，避免res出现重复

注意：
如果题目没有说明数的大小的话，我们就要用set来创建哈希表啦

Python代码：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hash = [0]*1002               #建立哈希表，后边的数大于1000都行
        res = []
        for i in nums1:               #对数组1遍历
            hash[i] = 1
        for i in nums2:               #对数组2遍历
            if hash[i] == 1 :         #表示两数组重复
                res.append(i)
                hash[i] = 0           #避免添入重复值 
        return res

力扣202. 快乐数

思路：

（1）建立set哈希表，记录每次新出现的和
（2）建立函数计算每次的数的和
（3）主函数判断和是否为1，为1返回True，出现重复的返回False，其他的就加入哈希表

Python代码：

class Solution:
    def isHappy(self, n: int) -> bool:
        def calculates(nums):             #从个位依次取值，平方求和
            sums = 0
            while nums:
                sums += (nums % 10)**2
                nums = nums//10
            return sums
        
        record = set()                     #建立哈希表，记录出现的和值

        while True:
            n = calculates(n)
            if n == 1:                    
                return True
            #如果出现重复，说明过程陷入死循环，返回False
            if n in record:   
                return False
            else:
                record.add(n)

力扣1. 两数之和

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路：

有两种思路方法：

1. 双指法法，让两个双指针对数组进行遍历，复杂度也就是O（n），这种方法别人没有想到，是一种比较创新而且较为简便的方法
2. 哈希表法，用哈希表记录每个数组的值和下标,遍历整个数组的时候顺便将其（值和下标），每次跟targe-value比较，直到出现之后相等的值即可

Python代码：

（1）双指针法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        slow,fast = 0,1
        while slow < len(nums)-1:
            if nums[slow]+nums[fast] == target:
                return [slow,fast]
            fast += 1
            if fast > len(nums)-1:
                slow += 1
                fast = slow + 1

（2）哈希表法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        for index,value in enumerate(nums):      #遍历数组，在record寻找是否有匹配的value
            if target-value in record:
                return [record[target-value],index]
            record[value] = index              #没有，将其记录在record中