hash相关题

面试

三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<3: return []
        nums.sort()
        res=set()
        for i , x in enumerate(nums[:-2]):
            if i>=1 and x==nums[i-1]:
                continue
            d={}
            for j in nums[i+1:]:
                # 判断 -（x+j）=j
                if j not in d:
                    d[-x-j]=1
                else:
                    res.add((x,-j-x,j))
        
        return map(list,res)

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Trie():

    def __init__(self):
        self.root={}
        self.end_word="#"

    def insert(self,word):
        node=self.root
        for char in word:
            node=node.setdefault(char,{})
        node[self.end_word]=self.end_word

    def find(self,word):
        node=self.root
        for char in word:
            if char not in node:
                return False
            node=node[char]
        return self.end_word in node

    def startWith(self,word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return True