文章目录

• • 一、哈希表
  • • 1.1 哈希表简介
    • 1.2 哈希函数
    • • 1.2.1 直接定址法
      • 1.2.2 除留余数法
      • 1.2.3 平方取中法
    • 2.4 基数转换法
    • 1.3 哈希冲突
    • • 1.3.1 开放地址法
      • 1.3.2 链地址法
    • 1.4 哈希表总结
  • 二、哈希表应用
  • • 2.1 哈希表题目列表
    • 2.2 设计哈希集合 、设计哈希映射
    • 2.3 存在重复元素I、II、III
    • • 2.3.1 存在重复元素
      • 2.3.2 存在重复元素 II
      • 2.3.3 存在重复元素 III
    • 2.4 只出现一次的数字
    • 2.5 有效的数独
    • 2.6 两数之和、三数之和、四数之和、四数相加
    • • 2.6.1 两数之和
      • 2.6.2 三数之和
      • 2.6.3 四数之和
      • 2.6.4 四数相加
    • 2.7 缺失的第一个正数
    • 2.8 最长连续序列
    • 2.9 根据字符出现频率排序
    • 2.10 字母异位词分组
    • 2.11 两个列表的最小索引总和
    • 2.12 字符串中的第一个唯一字符
    • 2.13 直线上最多的点数
    • 2.14 子域名访问计数

参考

• 《算法通关手册》-哈希表篇
• 【博文】散列表（上）- 数据结构与算法之美 - 极客时间

一、哈希表

1.1 哈希表简介

   哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。
   哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

哈希表的关键思想是使用哈希函数，将键 key 映射到对应表的某个区块中。我们可以将算法思想分为两个部分：

• 向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
• 在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。

哈希表的原理示例图如下所示：

  在上图例子中，我们使用 value = Hash(key) = key // 1000 作为哈希函数。// 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。

• 向哈希表中插入一个关键码值：通过哈希函数解析关键字，并将对应值存放到该区块中。
  • 比如：0138 通过哈希函数 Hash(key) = 0138 // 100 = 0，得出应将 0138 分配到0 所在的区块中。
• 在哈希表中搜索一个关键码值：通过哈希函数解析关键字，并在特定的区块搜索该关键字对应的值。
  • 比如：查找 2321，通过哈希函数，得出 2321 应该在 2 所对应的区块中。然后我们从 2 对应的区块中继续搜索，并在 2 对应的区块中成功找到了 2321。
  • 比如：查找 3214，通过哈希函数，得出 3214 应该在 3 所对应的区块中。然后我们从 3 对应的区块中继续搜索，但并没有找到对应值，则说明 3214 不在哈希表中。

哈希表在生活中的应用也很广泛，其中一个常见例子就是「查字典」。

比如为了查找 赞 这个字的具体意思，我们在字典中根据这个字的拼音索引 zan，查找到对应的页码为 599。然后我们就可以翻到字典的第 599 页查看 赞 字相关的解释了。

在这个例子中：

• 存放所有拼音和对应地址的表可以看做是 「哈希表」。
• 赞 字的拼音索引 zan 可以看做是哈希表中的 「关键字 key」。
• 根据拼音索引 zan 来确定字对应页码的过程可以看做是哈希表中的 「哈希函数 Hash(key)」。
• 查找到的对应页码 599 可以看做是哈希表中的 「哈希地址 value」。

1.2 哈希函数

哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希函数是哈希表中最重要的部分。一般来说，哈希函数会满足以下几个条件：

• 哈希函数应该易于计算，并且尽量使计算出来的索引值均匀分布。
• 哈希函数计算得到的哈希值是一个固定长度的输出值。
• 如果 Hash(key1) 不等于 Hash(key2)，那么 key1、key2 一定不相等。
• 如果 Hash(key1) 等于 Hash(key2)，那么 key1、key2 可能相等，也可能不相等（会发生哈希碰撞）。

  在哈希表的实际应用中，关键字的类型除了数字类，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。

  而关于整数类型的关键字，通常用到的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。下面我们介绍几个常用的哈希函数方法。

1.2.1 直接定址法

• 直接定址法：取关键字本身 / 关键字的某个线性函数值 作为哈希地址。即：Hash(key) = key 或者 Hash(key) = a * key + b，其中 a 和 b 为常数。

  这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。

  举一个例子，假设我们有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字，哈希函数取关键字自身，如下表所示。

比如我们想要查询 25 岁的人有多少，则只要查询表中第 25 项即可。

1.2.2 除留余数法

• 除留余数法：假设哈希表的表长为 m，取一个不大于 m 但接近或等于 m 的质数 p，利用取模运算，将关键字转换为哈希地址。即：Hash(key) = key % p，其中 p 为不大于 m 的质数。

  这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。

  比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中（长度为 11 的数组），通过除留余数法将这 7 个数应分别位于如下地址：

1.2.3 平方取中法

• 平方取中法：先通过求关键字平方值的方式扩大相近数之间的差别，然后根据表长度取关键字平方值的中间几位数为哈希地址。
  • 比如：Hash(key) = (key * key) // 100 % 1000，先计算平方，去除末尾的 2 位数，再取中间 3 位数作为哈希地址。

  这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。

2.4 基数转换法

• 基数转换法：将关键字看成另一种进制的数再转换成原来进制的数，然后选其中几位作为哈希地址。
  • 比如，将关键字看做是 13 进制的数，再将其转变为 10 进制的数，将其作为哈希地址。

以 343246 为例，哈希地址计算方式如下：

34324613=3×135+4×134+3×133+2×132+4×131+6×130=123511010343246_{13} = 3 \times 13^5 + 4 \times 13^4 + 3 \times 13^3 + 2 \times 13^2 + 4 \times 13^1 + 6 \times 13^0 = 1235110_{10}34324613​=3×135+4×134+3×133+2×132+4×131+6×130=123511010​

1.3 哈希冲突

哈希冲突（Hash Collision）：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，这种现象称为哈希冲突。

  理想状态下，我们的哈希函数是完美的一对一映射，即一个关键字（key）对应一个值（value），不需要处理冲突。但是一般情况下，不同的关键字 key 可能对应了同一个值 value，这就发生了哈希冲突。

  设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类：「开放地址法（Open Addressing）」 和 「链地址法（Chaining）」。

1.3.1 开放地址法

开放地址法（Open Addressing）：指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。

  当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1)。

• H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突（i = 1）时经过处理得到一个新地址 H(1)，如果在 H(1) 处仍然发生冲突（i = 2）时经过处理时得到另一个新地址 H(2) …… 如此下去，直到求得的 H(n) 不再发生冲突。
• Hash(key) 是哈希函数，m 是哈希表表长，对哈希表长取余的目的是为了使得到的下一个地址一定落在哈希表中。
• F(i) 是冲突解决方法，取法可以有以下几种：
  • 线性探测法：F(i)=1,2,3,...,m−1F(i) = 1, 2, 3, ..., m - 1F(i)=1,2,3,...,m−1。
  • 二次探测法：F(i)=12,−12,22,−22,...,±n2(n≤m/2)F(i) = 1^2, -1^2, 2^2, -2^2, ..., \pm n^2(n \le m / 2)F(i)=12,−12,22,−22,...,±n2(n≤m/2)。
  • 伪随机数序列：F(i)=伪随机数序列F(i) = 伪随机数序列F(i)=伪随机数序列。

  举个例子说说明一下如何用以上三种冲突解决方法处理冲突，并得到新地址 H(i)。例如，在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录（哈希函数为 Hash(key) = key % 11）。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5，产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

• 使用线性探测法：得到下一个地址 H(1) = (5 + 1) % 11 = 6，仍然冲突；继续求出 H(2) = (5 + 2) % 11 = 7，仍然冲突；继续求出 H(3) = (5 + 3) % 11 = 8，8 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 8 的位置。
• 使用二次探测法：得到下一个地址 H(1) = (5 + 1*1) % 11 = 6，仍然冲突；继续求出 H(2) = (5 - 1*1) % 11 = 4，4 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 4 的位置。
• 使用伪随机数序列：假设伪随机数为 9，则得到下一个地址 H(1) = (9 + 5) % 11 = 3，3 对应的地址为空，处理冲突过程结束，记录填入哈希表中序号为 3 的位置。

使用这三种方法处理冲突的结果如下图所示：

1.3.2 链地址法

链地址法（Chaining）：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。

链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法，链地址法更加简单。

我们假设哈希函数产生的哈希地址区间为 [0, m - 1]，哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T。

• 这样在插入关键字的时候，我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i，然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾，也可以在中间。如果每次插入位置为表头，则插入操作的时间复杂度为 O(1)O(1)O(1)。

• 而在在查询关键字的时候，我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i，然后将对应位置上的链表整个扫描一遍，比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)O(k)O(k)。对于哈希地址比较均匀的哈希函数来说，理论上讲，k = n // m，其中 n 为关键字的个数，m 为哈希表的表长。

  举个例子来说明如何使用链地址法处理冲突。假设现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函数为 Hash(key) = key % 13，哈希表的表长 m = 13，哈希地址范围为 [0, m - 1]。将这些关键字使用链地址法处理冲突，并按顺序加入哈希表中（图示为插入链表表尾位置），最终得到的哈希表如下图所示。

  相对于开放地址法，采用链地址法处理冲突要多占用一些存储空间（主要是链节点占用空间）。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中，待比较的关键字都是具有相同哈希地址的元素，而在开放地址法中，待比较的关键字不仅包含具有相同哈希地址的元素，而且还包含哈希地址不相同的元素。

1.4 哈希表总结

  本文讲解了一些比较基础、偏理论的哈希表知识。包含哈希表的定义，哈希函数、哈希冲突以及哈希冲突的解决方法。

• 哈希表（Hash Table）：通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
• 哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数。
• 哈希冲突（Hash Collision）：不同的关键字通过同一个哈希函数可能得到同一哈希地址。

哈希表的两个核心问题是：「哈希函数的构建」 和 「哈希冲突的解决方法」。

• 常用的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。
• 常用的哈希冲突的解决方法有两种：开放地址法和链地址法。

二、哈希表应用

2.1 哈希表题目列表

2.2 设计哈希集合 、设计哈希映射

• 0705. 设计哈希集合
• 0706 设计哈希映射

要求不使用内建的哈希表库，自行实现一个哈希集合（HashSet），满足以下操作：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

#输入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
#输出：
[null, null, null, true, false, null, true, null, false]#解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

思路：利用「数组+链表」的方式实现哈希集合
  定义一个一维长度为 buckets 的二维数组 table。第一维度用于计算哈希函数，为 key 分桶。第二个维度用于寻找 key 存放的具体位置。第二维度的数组会根据 key 值动态增长，模拟真正的链表。

class MyHashSet:def __init__(self):self.buckets = 1003self.table = [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef add(self, key: int) -> None:hash_key = self.hash(key)if key in self.table[hash_key]:return self.table[hash_key].append(key)def remove(self, key: int) -> None:hash_key = self.hash(key)if key not in self.table[hash_key]:return self.table[hash_key].remove(key)def contains(self, key: int) -> bool:hash_key = self.hash(key)return key in self.table[hash_key]

设计哈希映射和上一题其实是一样的，可以直接套用代码：

class MyHashMap:def __init__(self):self.buckets=1003 # 使用质数self.table=[[] for _ in range(self.buckets)]def put(self, key: int, value: int) -> None:hash_key,pos=self.hash(key)if not self.table[hash_key]:self.table[hash_key]=[-1]*self.bucketsself.table[hash_key][pos]=valuedef hash(self,key):#哈希函数，等同于将数字分为1000个桶return key%self.buckets,key//self.bucketsdef remove(self, key: int) -> None:hash_key,pos=self.hash(key)if self.table[hash_key]:        self.table[hash_key][pos]=-1def get(self, key: int) -> bool:hash_key,pos=self.hash(key)return -1 if self.table[hash_key]==[] else self.table[hash_key][pos]# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

2.3 存在重复元素I、II、III

• 0217 存在重复元素
• 0219 存在重复元素 II
• 0220 存在重复元素 III

2.3.1 存在重复元素

  给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false

return False if len(nums)==len(set(nums)) else True

2.3.2 存在重复元素 II

  给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
解法一：

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:d=set()for i in range(len(nums)):if nums[i] in d:return Trued.add(nums[i])if len(d)>k:d.remove(nums[i-k])return False

解法二：

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:d=dict()# 如果k值超过数组长度，将其赋值为数组长度-1，然后统计前k个数字的出现此数。# 如果某个元素已经出现在字典中，直接返回Trueif k>len(nums)-1:k=len(nums)-1l,r=0,kfor i in range(k+1):                        if nums[i] not in d:d[nums[i]]=d.get(nums[i],0)+1                    else:return True# 依次往右滑动窗口，每次删除左边界元素，加入右边界元素（次数+1）while r

class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:from sortedcontainers import SortedListk,t=indexDiff,valueDiffwindows=SortedList()for i in range(len(nums)):           if len(windows)>k:windows.remove(nums[i-k-1])windows.add(nums[i])# idx和i的区别是，idx是nums[i]在有序数组windows中的位置idx=windows.bisect_left(nums[i]) # 判断nums[i]和它在窗口中相邻的两个元素只差的绝对值，是否在t之内if idx>0 and abs(windows[idx]-windows[idx-1])<=t: # idx>0则idx-1最小为0return Trueif idx

 class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:bucket_dict = dict()for i in range(len(nums)):# 将 nums[i] 划分到大小为 t + 1 的不同桶中num = nums[i] // (t + 1)# 桶中已经有元素了if num in bucket_dict:return True# 把 nums[i] 放入桶中bucket_dict[num] = nums[i]# 判断左侧桶是否满足条件if (num - 1) in bucket_dict and abs(bucket_dict[num - 1] - nums[i]) <= t:return True# 判断右侧桶是否满足条件if (num + 1) in bucket_dict and abs(bucket_dict[num + 1] - nums[i]) <= t:return True# 将 i-k 之前的旧桶清除，因为之前的桶已经不满足条件了if i >= k:bucket_dict.pop(nums[i-k] // (t + 1))return False                       

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""sum=0for i in nums:sum^=ireturn sum

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

class Solution(object):def isValidSudoku(self, board):""":type board: List[List[str]]:rtype: bool"""row=[dict() for _ in range(9)] # 创建一个包含9个字典的列表，其中每个字典统计每一行元素出现的次数col=[dict() for _ in range(9)] # 统计每一列元素出现的次数box=[dict() for _ in range(9)] # 统计每个九宫格元素出现的次数for i in range(9):for j in range(9):               if board[i][j]=='.':continuenum=int(board[i][j])idx=(i//3)*3+j//3# 查找各行、各列、各九宫格中，是否出现过num这个元素。没有出现就返回0a,b,c=row[i].get(num,0),col[j].get(num,0),box[idx].get(num,0)if a!=0 or b!=0 or c!=0:return False# 在各行、列、九宫格中，将出现的数字次数计为1row[i][num]=1col[j][num]=1box[idx][num]=1return True

class Solution(object):def isValidSudoku(self, board):""":type board: List[List[str]]:rtype: bool"""for i in range(9):                        #对每一行进行判断row = []for j in range(9):if board[i][j] == '.':continueif board[i][j] in row:return Falseelse:row.append(board[i][j])for i in range(9):                         #对每一列进行判断col = []for j in range(9):if board[j][i] == '.':continueif board[j][i] in col:return Falseelse:col.append(board[j][i])for i in range(0,9,3):                 # 对每个九宫格进行判断for j in range(0,9,3):box=[]for x in range(3):for y in range(3):if board[i+x][j+y]=='.' :continueif board[i+x][j+y] in box:return Falseelse:box.append(board[i+x][j+y])return True

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""d=dict()for i in range(len(nums)):if target-nums[i] in d:return i,d[target-nums[i]]else:d[nums[i]]=ireturn False

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()ans=[]le=len(nums)for i in range(le):                     if nums[i]>0:breakif i>0 and nums[i]==nums[i-1]: # 如果下一位置和前一位置元素重复，就不需要再遍历continue    left,right=i+1,le-1#左指针起点i+1       while left0:right-=1elif nums[i]+nums[left]+nums[right]<0:left+=1else:ans.append([nums[i],nums[left],nums[right]])# 找到解之后，如果left或right下一个元素重复，则需要跳过重复位置while left!=right and nums[left]==nums[left+1]:left+=1while left!=right and nums[right]==nums[right-1]:right-=1# 找到解后也要移动指针left+=1right-=1return ans

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

class Solution(object):def fourSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[List[int]]"""nums.sort()le=len(nums)ans=[]for a in range(le):#if nums[a]>target:# break# 这里和三数之和不一样。三数之和nums[i]＞0，所有都是正数不用计算了。这里第一个数>target，还可以有负数使和变得更小if a>0 and nums[a]==nums[a-1]:continuefor b in range(a+1,le):if b>a+1 and nums[b]==nums[b-1]:continueleft,right=b+1,le-1while lefttarget:right-=1elif nums[a]+nums[b]+nums[left]+nums[right]

class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4):d=dict()count=0for i in nums1:for j in nums2:sum=i+jd[sum]=d.get(sum,0)+1for k in nums3:for l in nums4:               if -k-l in d:count+=d[-k-l]return count

输入：nums = [1,2,0]
输出：3

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:size = len(nums)for i in range(size):# 对于1到size范围内的数，才进行交换，放到正确位置while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:index1 = iindex2 = nums[i] - 1nums[index1], nums[index2] = nums[index2], nums[index1]for i in range(size):if nums[i] != i + 1:return i + 1return size + 1

class Solution(object):def longestConsecutive(self, nums):""":type nums: List[int]:rtype: int"""if len(nums)==0:return 0else:nums=list(set(nums)) # 去除重复元素nums.sort()left,right=0,1ans=1                # 默认起始的连续序列长度为1（只有一个元素时）# 如果差值不为1，左右指针右移；否则差值为1，右指针不停右移，同时记录连续序列的长度while left

class Solution(object):def longestConsecutive(self, nums):""":type nums: List[int]:rtype: int"""ans=0  # 记录最长序列长度nums=set(nums) # 去重for num in nums:if num-1 not in nums: # 比当前元素小1的不在集合中，则连续序列需要从头开始计算cur=numres=1 # 初始化连续序列长度=1while cur+1 in nums:cur+=1res+=1ans=max(ans,res)return ans

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

class Solution(object):def frequencySort(self, s):""":type s: str:rtype: str"""from collections import Counterd=dict(Counter(s)) # 统计每个字母出现的次数# 根据次数对字母进行降序排列，结果是一个列表d=sorted(d.items(),key=lambda x:x[1],reverse=True)ans=''for k,v in d:ans+=k*vreturn ans

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""d=dict()for ch in strs:# 子串进行字母排序，sorted的结果是一个列表，str将其转为字符串sort_ch=str(sorted(ch)) if sort_ch not in d:d[sort_ch]=[ch]else:d[sort_ch]+=[ch]ans=[]for k,v in d.items():ans+=[v]return ans

 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

class Solution:def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:d1 = dict()len1 = len(list1)len2 = len(list2)for i in range(len1):d1[list1[i]] = imin_sum = len1 + len2res = []for i in range(len2):if list2[i] in d1:sum = i + d1[list2[i]]if sum < min_sum:res = [list2[i]]min_sum = sumelif sum == min_sum:res.append(list2[i])return res

class Solution(object):def findRestaurant(self, list1, list2):""":type list1: List[str]:type list2: List[str]:rtype: List[str]"""d1=dict()ls=[]  # 存储相同字符res=[] # 存储相同字符的下标和ans=[] # 存储最终答案for i in range(len(list1)):d1[list1[i]]=ifor j in range(len(list2)):if list2[j] in d1:idx=d1[list2[j]]+j  # 相同字符的下标和ls.append(list2[j]) # 同步存储这个字符res.append(idx)      min_idx=min(res) # 最小下标和for i in range(len(res)):if res[i]==min_idx:ans.append(ls[i])return ans

输入: s = "leetcode"
输出: 0

class Solution(object):def firstUniqChar(self, s):""":type s: str:rtype: int"""d=dict()for ch in s:d[ch]=d.get(ch,0)+1 # 统计每个字符出现的次数for i in range(len(s)):if d[s[i]]==1:return ireturn -1

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

class Solution:def maxPoints(self, points: List[List[int]]) -> int:n = len(points)if n < 3:return nans = 0for i in range(n):line_dict = dict()line_dict[0] = 0same = 1for j in range(i+1, n):dx = points[j][0] - points[i][0]dy = points[j][1] - points[i][1]if dx == 0 and dy == 0:same += 1continuegcd_dx_dy = math.gcd(abs(dx), abs(dy))if (dx > 0 and dy > 0) or (dx < 0 and dy < 0):dx = abs(dx) // gcd_dx_dydy = abs(dy) // gcd_dx_dyelif dx < 0 and dy > 0:dx = -dx // gcd_dx_dydy = -dy // gcd_dx_dyelif dx > 0 and dy < 0:dx = dx // gcd_dx_dydy = dy // gcd_dx_dyelif dx == 0 and dy != 0:dy = 1elif dx != 0 and dy == 0:dx = 1key = (dx, dy)if key in line_dict:line_dict[key] += 1else:line_dict[key] = 1ans = max(ans, same + max(line_dict.values()))return ans

输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

class Solution:def subdomainVisits(self, cpdomains: List[str]) -> List[str]:if not cpdomains:return []times_dict = dict()for cpdomain in cpdomains:tiems, domain = cpdomain.split()tiems = int(tiems)domain_list = domain.split('.')for i in range(len(domain_list) - 1, -1, -1):sub_domain = '.'.join(domain_list[i:])if sub_domain not in times_dict:times_dict[sub_domain] = tiemselse:times_dict[sub_domain] += tiemsres = []for key in times_dict.keys():res.append(str(times_dict[key]) + ' ' + key)return res