哈希表


1.两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        for i,num in enumerate(nums):
            j=hashmap.get(target-num)
            if j != None :return [i,j]  # j可为0
            hashmap[num]=i

560.和为K的子数组

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre = {0:1} #记载所有前缀和
        ans,sum=0,0
        for num in nums:
            sum+=num
            need=sum-k
            if need in pre:
                ans += pre[need]
            #在hash table里查找key,如果有返回对应的value,反之返回0 
            pre[sum] = pre.get(sum, 0) + 1    
        return ans

小结

  1. 前缀和+hash的优化
  2. dict.get(key,default=None)

other

jewelsSet = set(J)
return sum(s in jewelsSet for s in S)

#集合是一个哈希表,降低遍历的时间复杂度
# 每次都遇到这个问题:
# unhashable type: 'list'
# 不能在哈希表中快速找到这个表,不能集合为多重表去重

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录