此处记录自己刷算法八股中的灵感，不会的题在此写下自己的感受和解题方法。目录的标题是主要使用的算法。
ref: LeetCode 热题100

哈希

复杂度为O(n)时常用，作用：O(n)建立，O(1)查找
对应的Python容器：dict(), collections.defaultdict()（即查找不到key时设置一个默认返回value）

最长连续序列（longest consecutive sequence）

题目要求：给定一个整数数组，在其中找到最长的连续序列的长度（数字的位置不一定相邻）。要求线性复杂度。
示例：

输入：nums=[100,4,200,1,3,2]
输出：4
解释：4, 1, 3, 2是最长的连续序列，长度为4。

思路：好吧真没啥思路……排序算法就得吃掉O(n\mathrm{log}n)的复杂度；但是一个个找升序元素的话最终会消耗O(n^2)，铁铁的TLE
看完题解的哈希表后自信满满地选择性添加键值对（即x若在字典中没有键x-1则添加键x），在用例[0,-1]时报错……崩溃了

题解：（内心OS这也能哈希？）既然要找升序元素，那么哈希表就可以很方便找啦。把数组中的一些元素哈希到表里√
但是如果对每个元素x都要找x+1，那么又回到了上面的“一个个找元素”，复杂度仍是平方。既然题目只要求输出长度，那么直接用长度作为哈希表的值就可以啦！目标就是构建字典{x: x开始的最长连续序列长度}。为了摆脱“对每个x都要找元素”，我们加入判断：对于每个x，它是否是序列开始的元素？若是，则x往后的元素对应的值都+1；否则，x对应的值先默认为1。
首先将数组哈希一遍，并让哈希表的值全1；然后遍历哈希表，若x在哈希表中有对应的元素x-1，则键x对应的值+1，且键x+1, x+2……对应的值也+1，直到键不存在。

代码：

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        arr = {} # arr[nums中的数字]=从它开始的最长连续序列长度
        nums = list(set(nums)) # 去重
        for i in nums:
            arr[i] = 1 # 默认从i开始的排列长度为1
        for i in nums:
            if i-1 not in arr.keys(): # 如果是开头
                next = i+1
                while next in arr.keys():
                    arr[i] += 1
                    next += 1
        return max(arr.values())