哈希表

1. 两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h = {}
        for i, num in enumerate(nums):
            if (k := target-num) in h:
                return [h[k], i]
            h[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
# 前缀和+hash的优化
# `dict.get(key,default=None)`

149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ans = 1
        for i in range(len(points)):
            d = {}
            for j in range(i):
                u = points[i][1]-points[j][1]
                v = points[i][0]-points[j][0]
                if v==0:
                    d['max'] = d.get('max',0)+1
                else:
                    k = u/v*1.0
                    d[k] = d.get(k,0)+1
            if d:
                ans = max(ans,max(d.values())+1)
        return ans

692. 前K个高频单词

from functools import cmp_to_key
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        def func(x,y):
            w1, c1 = x
            w2, c2 = y
            if c1>c2:
                return -1        #次数高的在前面
            elif c1==c2:         #次数相等的，字母序低的在前面
                return -1 if w1<w2 else 1
            else:
                return 1

        ans = Counter(words).most_common()
        ans.sort(key = cmp_to_key(lambda x,y:func(x,y)))
        return [i[0] for i in ans][:k]

other

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

#集合是一个哈希表，降低遍历的时间复杂度

# 关于报错：
#          unhashable type: 'list'
# 不能在哈希表中快速找到这个表，不能集合为多重表去重