哈希表.md

739，每日温度，中等

核心方法：维护一个数组nxt，记录每个温度第一次出现的下标，数组中的元素初始化为无穷大，在遍历过程中更新nxt的值；反向遍历数据，对于每个遍历到的元素，从nxt中找到从这个元素到100中每个温度第一次出现的下标，找到的下标减去当前的元素下标即为下一次比当天高的等待天数，最后向nxt中加入新确定的温度和对应的下标

• 复杂度：
  • 时间复杂度：O(mn)，其中n是温度列表的长度，m是数组nxt的长度
  • 空间复杂度：O(m)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n = len(T)
        ans, nxt, big = [0] * n, dict(), 10**9
        for i in range(n - 1, -1, -1):  # 从尾向前遍历
            warmer_index = min(nxt.get(t, big) for t in range(T[i] + 1, 102))  # 求所有大于当前温度的最小下标位置
            if warmer_index != big:
                # 如果这个下标不等于无穷大，则等待天数就是找到的温度的下标-当前温度下标
                ans[i] = warmer_index - i
            nxt[T[i]] = i  # 更新nxt表
        return ans

• （推荐）核心方法：使用单调栈，元素索引入栈，进栈规则为：1、栈为空，2、当前温度比栈顶温度低时；如果当前温度比栈顶温度高，那么栈顶元素出栈，天数就是当前温度对应索引-栈顶元素索引，直到所有小的栈顶元素全部出栈，然后将当前元素索引入栈
• 复杂度分析
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n = len(T)
        res = [0] * n
        stack = []
        for i in range(n):
            tmp = T[i]
            while stack and T[stack[-1]] < tmp:
                idx = stack.pop()
                res[idx] = i - idx
            stack.append(i)
        return res

136，只出现一次的数据，简单

核心方法：使用字典记录元素出现的频率

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = dict()
        for i in range(len(nums)):
            if nums[i] not in freq.keys():
                freq[nums[i]] = 1
            else:
                freq[nums[i]] += 1
        for k, v in freq.items():
            if v == 1:
                return k

异或运算 （位操作）

• 异或运算的三个性质：

  • 任何数与自己异或等于0
  • 任何数与0异或等于自己
  • 异或运算满足交换律和结合律
  • 假设共有2m+1个数，只有一个是出现一次的，那么使用异或运算(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(a m⊕a m)⊕a m+1，最后等于a m+1，结果就是出现一次的数

• 时间复杂度：O(n)

• 空间复杂度：O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

18，四数之和，中等

核心方法：排序，双指针，

难点：数组排序，首先使用两重循环取出数组中的前两个数，然后使用双指针遍历后面的数，如果遇到与前面相同的数，则跳过，这样可以避免出现重复四元组；还可以添加一些剪枝操作；假设前面两层循环确定的数为i和j，那么左指针为j+1，右指针为length-1。

复杂度分析：

• 时间复杂度：O(n^3)，其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，枚举四元组的时间复杂度是 O(n^3)，因此总时间复杂度为 O(n^3 +nlogn)=O(n^3 )。
• 空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为 O(n)。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        quadruplets = list()
        if not nums or len(nums) < 4:
            return quadruplets
        
        # 排序
        nums.sort()
        length = len(nums)
        for i in range(length - 3):
            # 这里设置 length-3 是为了后面还要留出3位
            if i > 0 and nums[i] == nums[i - 1]:
                # 和前一个一样，就跳过
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                # 剪枝，如果挨着的四数之和已经大于target，后面如何遍历都不会等于target，退出循环
                break
            if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
                # 剪枝，第一位和后三位的和已经小于target，遍历中间也不会等于target，跳过
                continue
            for j in range(i + 1, length - 2):
                # 和上一重循环内容相同，处理方式相同
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left, right = j + 1, length - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            # 注意需要保证移动后，左指针要小于右指针
                            # 和移动方向的下一个一样，就跳过
                            left += 1
                        left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            # 和移动方向的下一个一样，就跳过
                            right -= 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        
        return quadruplets

49，字符异位词分组，中等

核心方法：对每个字符串进行排序，作为分组的标志字符串（键），将每组的结果添加到这个键对应的列表值中

时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度。需要用哈希表存储全部字符串。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            mp[key].append(key)
        return list(mp.values())

核心方法：由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。

空间复杂度：O(n(k+∣Σ∣))，记录每个字符串内每个字母出现次数需要Σ，且元组中需要k个位置作为键

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            counts = [0] * 26  # 使用固定大小的数组来记录每个字符串出现的次数
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)
        
        return list(mp.values())

347，前K个高频元素，中等

核心方法：首先对nums做元素-频率字典，然后对字典的value进行降序排序，然后取出前k个

时间复杂度：排序的时间复杂度为O(nlogn)

空间复杂度：新建了一个字典，字典长度最大为n，所以O(n)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = dict()
        for n in nums:
            if n not in freq.keys():
                freq[n] = 1
            else:
                freq[n] += 1
        freq_ = sorted(list(freq.items()), key=lambda x:x[1], reverse=True)
        res = []
        for i in range(k):
            res.append(freq_[i][0])
        return res

349，两个数组的交集，简单

核心方法：使用set集合来做

时间复杂度：O(m+n)，m和n分别为两个数组的长度，使用两个集合分别存储两个数组中的元素需要 O(m+n) 的时间

空间复杂度：O(m+n)，空间复杂度主要取决于两个集合。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return self.set_intersection(set1, set2)

    def set_intersection(self, set1, set2):
        if len(set1) > len(set2):
            return self.set_intersection(set2, set1)
        return [x for x in set1 if x in set2]

核心方法：排序+双指针

难点：两个指针遍历两个数组，起始分别指向两个数组的头部，每次比较两个指针的两个数组中的数字，如果不相等，移动较小值的那个指针，如果相等，则需要判断这个值是否等于上一个加入结果列表中的值，不等于则加入结果列表，两个指针同时右移

时间复杂度：排序，O(mlogm+nlogn)

空间复杂度：O(logm+logn)，空间复杂度主要取决于排序使用的额外空间。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        length1, length2 = len(nums1), len(nums2)
        intersection = list()
        index1 = index2 = 0
        while index1 < length1 and index2 < length2:
            num1 = nums1[index1]
            num2 = nums2[index2]
            if num1 == num2:
                # 保证加入元素的唯一性，新加入的数要小于上一个加入列表中的数
                if not intersection or num1 != intersection[-1]:
                    intersection.append(num1)
                index1 += 1
                index2 += 1
            elif num1 < num2:
                # 移动值小的那一个指针
                index1 += 1
            else:
                index2 += 1
        return intersection

3，无重复字符的最长子串，中等

核心方法：双指针，使用滑动窗口。

难点：初始右指针指向-1的位置，每一次移动右指针，如果右指针指向的元素不在窗口内，则将这个元素添加到字符子串内，后移右指针直到遇到重复的字符；此时删除掉子串中的第一个元素，重复上述步骤，直到遍历完整个字符串。这里所说的左指针，其实就是遍历字符串所用的 i，窗口范围就是[i, rk]组成的

时间复杂度：O(n)

空间复杂度：O(∣Σ∣)，∣Σ∣ 表示字符集的大小

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 使用一个字典（滑动窗口）来判断每个字符是否出现过
        S = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        # ans 表示最长子串
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一个位置，移除一个字符，即删除掉窗口内的最左边的字符
                S.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in S:
                # 不断地移动右指针，要保证rk右移后不能溢出，且新加入的字符是不在现存的字符串中
                S.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

560，和为k的子数组，中等

**核心方法：**我们定义 $\textit{pre}[i]$ 为 $[0..i]$ 里所有数的和，则 $\textit{pre}[i]$ 可以由 $\textit{pre}[i-1]$ 递推过来，即

$pre[i]=pre[i−1]+nums[i]$

那么 $[j..i]$ 这个子数组和为 $k$ 这个条件可以转化为

$pre[i]-pre[j−1]==k$，移项后 $pre[j-1]==pre[i]-k$

所有只需要统计以 $i$ 结尾的和为 $k$ 的连续子数组个数时，有多少个前缀和为 $pre[i]-k$ 的 $pre[j]$ 即可

• 时间复杂度：O(n)
• 空间复杂度：O(∣Σ∣), ∣Σ∣为所有和的个数

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        # mp定义的是，以nums中每个数结尾的所有数的和作为键，对应值为这个和出现的次数
        mp = collections.defaultdict(int)
        mp[0] = 1
        Sum = 0
        for i in range(len(nums)):
            Sum += nums[i]
            if Sum - k in mp:
                count += mp[Sum - k]
            mp[Sum] += 1  # 这一句比较关键，因为设置了collections.defaultdict(int)
            # 这一句对应两种情况，一种是某cur_sum之前出现过（直接在原来出现的次数上+1即可），
            # 另一种是某cur_sum没出现过（理论上应该设为1，但是因为此处用defaultdict存储，如果cur_sum这个key不存在将返回默认的int，也就是0）
        return count

37，解数独，困难

核心方法：经典回溯法

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:

        nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
        row = [set() for _ in range(9)]  # 每行设置9个集合
        col = [set() for _ in range(9)]  # 每列设置9个集合
        palace = [[set() for _ in range(3)] for _ in range(3)]  # 设置3*3宫格的集合
        blank = []

        # 初始化，按照行、列、宫 分别存入哈希表
        for i in range(9):
            for j in range(9):
                ch = board[i][j]  # 取出每个位置的字符
                if ch == ".":  # 如果这个位置的字符等于'.'，则将这个位置坐标添加到blank中
                    blank.append((i, j))
                else:
                    row[i].add(ch)  # 否则，将这个字符添加进对应行，列，宫格的集合中
                    col[j].add(ch)
                    palace[i//3][j//3].add(ch)

        def dfs(n):
            if n == len(blank):  # 已经处理完最后一个空位置了，回溯停止
                return True
            i, j = blank[n]  # 取出当前空位置的行，列坐标
            rst = nums - row[i] - col[j] - palace[i//3][j//3]  # 去掉行列宫里的所有数字后剩余的数字集合
            if not rst:  # 如果没得选了，就返回错误，这么选不行
                return False
            for num in rst:
                # 从可选的里面进行选取，选定后，将这个数添加进行列宫里面
                board[i][j] = num
                row[i].add(num)
                col[j].add(num)
                palace[i//3][j//3].add(num)
                # 继续处理下一个位置
                if dfs(n+1):
                    return True
                # 如果下一个位置已经不对了，那么需要做撤回操作
                row[i].remove(num)
                col[j].remove(num)
                palace[i//3][j//3].remove(num)

        dfs(0)

387，字符串中的第一个唯一字符，简单

• 时间复杂度：O(N)
• 空间复杂度：O(N)

class Solution:
    def firstUniqChar(self, s: str) -> int:
        dic = {c: s.count(c) for c in set(s)}
        for i, c in enumerate(s):
            if dic[c] == 1:
                return i
        return -1

核心方法：find() 和 rfind()

• 时间复杂度：O(N)
• 空间复杂度：O(1)

class Solution(object):
    def firstUniqChar(self, s: str) -> int:
        # 先假设最小索引为最后的字符索引
        min_unique_char_index = len(s)

        # 已知字符串由小写字母构成，则遍历a-z
        for c in "abcdefghijklmnopqrstuvwxyz":
            i = s.find(c)  # 如果包含子字符串，返回第一次出现的索引值，否则返回-1
            # 分别从目标的字符串头和字符串尾查找对应字母的索引；如果两索引相等，则说明是单一字符
            if i != -1 and i == s.rfind(c):
                # s.rfind(c) 表示c在s中最后一次出现的位置
                # 更新最新的最小索引
                min_unique_char_index = min(min_unique_char_index, i)

        # 如果返回值不为最后字符的索引，则返回最小索引值
        # 否则，根据题意，返回-1
        return min_unique_char_index if min_unique_char_index != len(s) else -1

454，四数相加，中等

核心方法：分组+哈希表

难点：将两个数组的每两个数的和作为键，和的次数作为值，建立【和-次数】字典；每次从后两个数组中各选取两个数，看他们的和的负数是否是字典中的键，如果是，就把键对应值累加到结果中

时间复杂度：O(n^2)

空间复杂度：O(n^2)

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        countAB = collections.Counter(u+v for u in nums1 for v in nums2)
        ans = 0
        for m in nums3:
            for n in nums4:
                if -(m+n) in countAB:
                    ans += countAB[-(m+n)]
        return ans

409，最长回文串，简单

核心方法：如果数组中有的字符出现的次数为n，那么可利用的个数就为 n // 2 * 2，// 表示整除，长度中每次更新 n // 2 * 2个数（也就是说如果这个元素能够成为回文串的一部分，那么其能够贡献的元素长度就是 n // 2 * 2个）；在上述条件下，如果出现次数为奇数，则这个奇数可以作为回文的中心，长度数更新+1，其他出现奇数次的数就不能作为中心了

时间复杂度：O(n)

空间复杂度：O(s)，s为set集的大小

class Solution:
    def longestPalindrome(self, s: str) -> int:
        ans = 0
        count = collections.Counter(s)
        for v in count.values():
            # 如果回文串长度非偶数时，取到元素个数为奇数的，对回文串的贡献为0
            # 取到元素个数为偶数的，对回文串的贡献为 v // 2 * 2
            ans += v // 2 * 2
            if ans % 2 == 0 and v % 2 == 1:
                # 一旦回文串的长度为偶数（非零），那么最多取一个奇数，回文长度+1
                # 后续如果再遍历到元素个数为奇数的，回文串长度就不会再加了，因为长度不为偶数
                ans += 1
        return ans

895，最大频率栈，困难

核心方法：哈希表

pop时需要满足两个条件，一个是推出的元素要是频率最大的，另一个是频率相同时推出最近入栈的。

这里维护两个哈希表，一个是freq，用来记录元素-频率，能够在O(1)复杂度内查到元素频率，另一个是group，来记录出现频率的数和对应的元素，也就是一个频率可能对应多个元素。

注意：当由于弹出操作，不同类型的元素个数发生变化，导致最大频率也跟着变化时，在弹出完成后需要判断当前最大元素对应的列表是否为空，如果为空，就要减小最大频率。

• 时间复杂度：入栈和出栈都是O(1)
• 空间复杂度：两个哈希表，长度都是n，O(n)

class FreqStack:
    def __init__(self):
        self.freq = collections.Counter()  # 记录元素-频率的映射
        self.group = collections.defaultdict(list)  # 记录频率-拥有这个频率的元素的映射，也就是说一个频率可能对应多个元素
        self.max_freq = 0  # 最大频率


    def push(self, val: int) -> None:
        # 更新频率，已有频率基础上+1
        f = self.freq[val] + 1
        self.freq[val] = f 
        # 更新最大频率
        if f > self.max_freq:
            self.max_freq = f
        self.group[f].append(val)

        
    def pop(self) -> int:
        print(self.group)
        print(self.max_freq)
        # 找到最大频率下对应的最新的元素，减小对应频率
        x = self.group[self.max_freq].pop()
        self.freq[x] -= 1
        # 判断最大频率对应列表是为空，如果为空，当前最大频率应该为减小
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return x


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()

146，LRU缓存机制，中等

核心方法，要求查找get和插入put的时间复杂度都为O(1)，那么应该使用哈希链表，这里是哈希+双链表。

其中哈希表中的键值对是key-node，双链表的头节点表示最近操作过的节点，尾节点为最后操作过的节点，需要自己手动实现。

get和put方法需要调用以下4个函数

• 加入头节点
• 移除某个节点
• 将某节点提至头节点
• 删掉尾部节点

对于get方法，首先判断查找key是否在哈希中，如果不在直接返回-1；在的话通过哈希表得到key的node，将node提至队列的头部，并返回node值；

对于put方法，首先判断查找key是否在哈希中，如果不在，需要根据键值对创建新的node，然后在哈希中创建key-node关系，并将新node加入至队列头部，队列长度+1。注意，如果长度大于容量，那么在队尾（最不常用的）删除一个节点，并同时在哈希表中删掉对应的key-node，队列长度-1；如果查找key在哈希中，先通过哈希表找到这个节点，修改值，然后提至头部

• 时间复杂度：O(1)
• 空间复杂度：O(1)

class DLinkedNode():
    # 初始化双链表的数据结构
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()  # 使用哈希存储key
        # 使用伪头和伪尾节点，初始化一个双链表
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        # capacity 表示缓存的容量
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            # 如果不存在，直接返回-1
            return -1
        # 获取key的值，先通过哈希表定位，再移到头部即可
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果哈希表中没有这个key，就创建新的节点
            node = DLinkedNode(key, value)
            # 将key与新节点加入哈希表中
            self.cache[key] = node
            # 新节点加入到链表
            self.addToHead(node)
            # 双链表长度+1
            self.size += 1
            if self.size > self.capacity:
                # 双链表长度大于容量的，要删掉队尾的节点
                removed = self.removeTail()
                # 对应删掉哈希表中的键值对，双链表长度-1
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果已经存在了，先通过哈希表找到这个节点，修改值，然后提至头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(self, node):
        # 在头节点处增加一个节点
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        # 要删除一个node
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        # 将一个节点移到最近使用的位置
        # 现在原序列中删掉这个节点，再重新添加进去
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        # 删掉尾部节点
        node = self.tail.prev
        self.removeNode(node)
        return node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

383，赎金信，简单

核心方法：哈希表，记录magazine中每个字符的频率，在遍历randomNotes时，判断当前字符是否出现在剩余的magzine当中，如果没有了，就返回false

n, m 分别为magzine和randomNotes的长度

时间复杂度：max(O(nlogn), m)，使用Counter带了一层排序

空间复杂度：O(n) 哈希表的最坏情况下

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        
        count = collections.Counter(magazine)
        print(count)
        for i in range(len(ransomNote)):
            if ransomNote[i] not in magazine:
                return False
            else:
                if count[ransomNote[i]] < 1:
                    return False
                count[ransomNote[i]] -= 1
        return True

128，最长连续序列，中等

核心方法：排序

先对数组进行排序，然后判断每次遍历元素时，判断当前元素是否只比前面大1，如果是长度加1，否则长度置为1，也就是从头开始计数。全程维护一个最大长度，用于返回结果

时间复杂度：O(nlogn)

空间复杂度：O(1)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 对数组进行排序，然后一次遍历，
        # 维护一个最大长度，后一个元素比前一个元素只大1，那么最大长度+1
        if not nums:
            return 0
        nums.sort()
        length = 1
        last = nums[0]
        max_len = 1
        for i in range(1, len(nums)):
            if nums[i] == last + 1:
                length += 1
            elif nums[i] == last:
                continue
            else:
                length = 1
            max_len = max(length, max_len)
            last = nums[i]
        return max_len

 推荐 核心方法：使用哈希表，根据遍历进行查找的时间复杂度能够降为O(1)，遍历只需O(n)；使用集合对数组所有元素进行去重，然后便利这个数组，去找当前元素减1之后的值是否在集合中，如果在，就可以跳过；如果不在，则记录当前长度为1，然后继续探索（while中的条件）当前数加1是否在集合中，全程维护最大长度。

时间复杂度：O(n)

空间复杂度：O(n)

def longestConsecutive(self, nums: List[int]) -> int:
    max_len = 0
    nums_set = set(nums)  # 数组转为集合
    for num in nums_set:  # 遍历集合
        if num - 1 not in nums_set:  
            # 判断前一个数是否不在集合中，这里的目的是想找到一个连续序列的起始位置
            # 然后从起始位置开始寻找连续序列的最大长度
            cur_num = num
            length = 1
            while num + 1 in nums_set:
                length += 1
                num += 1
                max_len = max(max_len, length)
	return max_len

448，找到所有数组中消失的数字，简单

核心方法：哈希表

所有数组都是从1开始，所以使用哈希表对数组内的数字进行去重。然后遍历数组，找到不在集合中的数字即可。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        set_nums = set(nums)
        res = list()
        for i in range(1, n+1):
            if i not in set_nums:
                res.append(i)
        return res

核心方法：由于数组中的数字全部都是在[1, n]之间的，遍历每个位置的数x，将nums[x-1]的值加上8，那么在遍历完成后，缺少的数的位置，也就是没有加上8的位置，就一定是重复数出现的位置-1，那么第二次遍历就可以把这个位置找出来

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            # 为了防止有些位置已经是加过8的，所以这里需要对n取余就能把原来的数还原回来
            x = (num - 1) % n
            nums[x] += n
        # 第二次遍历，如果该位置的数小于8，返回索引+1
        ret = [i + 1 for i, num in enumerate(nums) if num <= n]
        return ret