CodeTop - Top 10

题目	简述、方案、死人坑
无重复字符的最长子串	这里我们用双指针加哈希表或集合，遇到就循环移除
反转链表	迭代法：nxt->cur.next->nxt.next->pre.next->nxt 递归法：双终止->递归下一个->头下下->头下
LRU 缓存	哈希表加上双向链表，理论不难但是特别容易出错。我的想法是把只实现两个辅助函数，一个`add`一个`remove`，其中每一个函数要封装到一起，不要把功能拆出去。哈希表用的是`del hash[key]`。
数组中的第K个最大元素	快选法：分治，分成大于和小于pivot点的两部分分割`pivot`用的是`l`和`r`指针，终止后`j`指针指向左侧边界（包含）最大堆：建立一个堆，需要实现以下几个函数，`down`+`pop`+`bigger`+`swap`+`son`+`parent`+序列建堆，另外`up`和`push`可以不用
K 个一组翻转链表	迭代法：nxt->cur.next->nxt.next->pre.next->nxt，先遍历一遍找到`group`组数
三数之和	先排序，再双指针，中间记得去重对`i`去重，我们只要第一个不同的`i`，其他的全部略过对`j`和`k`去重，我们如果命中，则`j`和`k`都要更新到不同的下一个
最大子数组和	Kadane算法，用short和long来遍历 `short = max(num, num + short)` `long = max(long, short)`
手撕快排	循环完要分治递归啊！！！血泪教训，`l->j`和 `j+1->r`
合并两个有序链表	罕见的简单题
最长回文子串	扩展法：最容易错的是指针方向，这两个是往外走，`l, r = l - 1, r + 1` 动态规划：也可以，但是和扩展法的复杂度是一样的

无重复字符的最长子串

3. 无重复字符的最长子串

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

方案一：双指针+哈希集合

这道题可以使用 滑动窗口 的思想来解决。滑动窗口是一种常见的用于解决数组/字符串子串问题的技巧。我们维护一个窗口，窗口的左右边界分别是 left 和 right，表示当前子串的起始和结束位置。我们使用一个哈希集合（set）来记录当前窗口内的字符。

初始化：left 和 right 都从 0 开始，表示窗口的初始位置。max_len 用于记录最大子串的长度。
移动右边界：将 s[right] 加入哈希集合，并向右移动 right。
处理重复字符：如果 s[right] 已经在哈希集合中，说明遇到了重复字符，此时需要移动 left 指针，直到将重复字符移出窗口。
更新最大长度：在每一步移动 right 后，更新 max_len。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # 记录一个集合统计窗口内的数字
        char_set = set()
        left = 0
        max_len = 0

        # 遍历整个字符串
        for right in range(0, len(s)):

            # 重合则移除直到单一
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            
            # 无条件添加元素并计算
            char_set.add(s[right])
            max_len = max(max_len, right-left+1)

        return max_len

方案二：双指针 + 哈希映射

思路：使用哈希映射（字典）来记录字符最后一次出现的位置。当遇到重复字符时，left 指针可以直接跳转到重复字符的下一个位置，而不需要逐步移动。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # 使用字典来记录字符最后出现的位置
        char_map = {}
        left = 0
        max_len = 0

        # 遍历整个字符串
        for right in range(0, len(s)):
            if s[right] in char_map and char_map[s[right]] >= left:
                # 如果字符在字典中且在当前窗口内，移动左指针
                left = char_map[s[right]] + 1
            
            # 更新字符的最新位置
            char_map[s[right]] = right
            
            # 更新最大长度
            max_len = max(max_len, right - left + 1)

        return max_len

时空复杂度分析

时间复杂度: O(n)，其中 n 是字符串的长度。left 和 right 指针最多各移动 n 次。
空间复杂度: O(min(m, n))，其中 m 是字符集的大小。在最坏情况下，哈希集合或哈希表的大小为 min(m, n)。

LRU缓存

146. LRU 缓存

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

方案：哈希表+双向链表

为了实现 O(1) 时间复杂度的 get 和 put 操作，我们需要结合 哈希表（快速查找）和 双向链表（维护数据顺序）来实现 LRU 缓存。具体思路如下：

双向链表：
- 链表中的节点按访问时间排序，最近访问的节点放在链表头部，最近最少使用的节点放在链表尾部。
- 链表的插入和删除操作时间复杂度为 O(1)。
哈希表：
- 哈希表存储键和对应的链表节点的指针，便于快速查找和更新。
操作逻辑：
- get(key)：如果键存在，通过哈希表找到节点，将其移动到链表头部（表示最近使用），并返回值；如果键不存在，返回 -1。
- put(key, value)：如果键存在，更新节点的值，并将其移动到链表头部；如果键不存在，创建新节点并插入链表头部，同时检查容量是否超过限制，如果超过则删除链表尾部的节点。

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76


class Node:
    def __init__(self, key=0, value=0):
        """
        双向链表节点类。
        :param key: 节点的键，默认为 0。
        :param value: 节点的值，默认为 0。
        """
        self.key = key  # 节点的键
        self.value = value  # 节点的值
        self.prev = None  # 前驱节点，指向前一个节点
        self.next = None  # 后继节点，指向下一个节点


class LRUCache:
    def __init__(self, capacity: int):
        """
        初始化 LRU Cache。
        :param capacity: 缓存容量。
        """
        self.capacity = capacity  # 缓存的最大容量
        self.cache = {}  # 缓存字典，用于存储键值对
        self.head = Node()  # 双向链表的虚拟头节点
        self.tail = Node()  # 双向链表的虚拟尾节点
        self.head.next = self.tail  # 初始化链表，头节点指向尾节点
        self.tail.prev = self.head  # 尾节点指向头节点

    def remove(self, node):
        """
        从双向链表和缓存字典中移除指定节点。
        :param node: 要移除的节点。
        """
        node.prev.next = node.next  # 修改前驱节点的后继指针
        node.next.prev = node.prev  # 修改后继节点的前驱指针
        del self.cache[node.key]  # 从缓存字典中移除该节点的键值对

    def add(self, node):
        """
        将节点添加到双向链表的头部，并加入缓存字典。
        :param node: 要添加的节点。
        """
        node.next = self.head.next  # 新节点的后继指针指向原链表的第一个节点
        node.prev = self.head  # 新节点的前驱指针指向虚拟头节点
        self.head.next.prev = node  # 原链表的第一个节点的前驱指针指向新节点
        self.head.next = node  # 虚拟头节点的后继指针指向新节点
        self.cache[node.key] = node  # 将节点加入缓存字典

    def get(self, key: int) -> int:
        """
        获取缓存中指定键对应的值，并将该节点移动到链表头部（表示最近使用）。
        :param key: 要查找的键。
        :return: 如果键存在，返回对应的值；否则返回 -1。
        """
        if key in self.cache:
            node = self.cache[key]  # 从缓存字典中获取节点
            self.remove(node)  # 从链表中移除该节点
            self.add(node)  # 将该节点添加到链表头部
            return node.value  # 返回节点的值
        else:
            return -1  # 键不存在，返回 -1

    def put(self, key: int, value: int) -> None:
        """
        插入或更新缓存中的键值对。如果缓存已满，则移除最久未使用的节点。
        :param key: 要插入或更新的键。
        :param value: 要插入或更新的值。
        """
        if key in self.cache:
            node = self.cache[key]  # 从缓存字典中获取节点
            self.remove(node)  # 从链表中移除该节点
            node.value = value  # 更新节点的值
            self.add(node)  # 将节点添加到链表头部
        else:
            node = Node(key, value)  # 创建新节点
            self.add(node)  # 将节点添加到链表头部
            if len(self.cache) > self.capacity:  # 如果缓存超出容量
                self.remove(self.tail.prev)  # 移除链表的最后一个节点

时空复杂度分析

时间复杂度：
- get 和 put 操作的时间复杂度均为 O(1)，因为哈希表的查找、插入和删除操作均为 O(1)，双向链表的插入和删除操作也为 O(1)。
空间复杂度: O(capacity)，其中 capacity 是缓存的容量。哈希表和双向链表的空间复杂度均为 O(capacity)。

易错点

哈希表与链表的同步更新：别他妈忘了这两个要同步更新
哈希表的删除和添加：这个贼容易错，我之前就错过

反转链表

206. 反转链表

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

方法一：当前不动，后移动到前

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 如果链表为空，直接返回
        if not head:
            return head 
      
        # 创建一个哑节点(dummy)，用于简化操作
        dummy = ListNode(-1, head)
        # cur指向当前节点，prv指向当前节点的前一个节点
        cur, prv = head, dummy 
      
        # 遍历链表，反转节点
        while cur.next:
            nxt = cur.next  # 保存当前节点的下一个节点
            cur.next = nxt.next  # 将当前节点的next指向nxt的下一个节点
            nxt.next = prv.next  # 将nxt的next指向prv的next节点
            prv.next = nxt  # 将prv的next指向nxt
      
        # 返回反转后的链表头节点
        return dummy.next 

时空复杂度

时间复杂度: O(n)，其中 n 是链表的长度。我们需要遍历链表中的每个节点一次。
空间复杂度: O(1)，我们只使用了常数个额外的指针，没有使用额外的空间。

易错点

边界条件处理：如果链表为空，直接返回 head。
指针操作顺序：在反转节点时，指针的操作顺序非常重要，错误的顺序可能导致链表断裂或死循环。
返回值：最终返回的是 dummy.next，而不是 prv 或 cur。

方法二：递归法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件：如果链表为空，或者链表只有一个节点，直接返回 head
        if not head or not head.next:
            return head
        
        # 递归调用，反转从 head.next 开始的链表
        # p 是反转后的新链表的头节点
        p = self.reverseList(head.next)
        
        # 将当前节点的下一个节点的 next 指向当前节点，实现反转
        head.next.next = head
        
        # 将当前节点的 next 置为 None，避免链表成环
        head.next = None
        
        # 返回反转后的链表的头节点
        return p

举例说明

假设链表为 1 -> 2 -> 3 -> 4 -> 5，递归过程如下：

递归到 5，满足终止条件，返回 5。
回溯到 4：
- 4.next.next = 4，即 5.next = 4。
- 4.next = None。链表变为：5 -> 4。
回溯到 3：
- 3.next.next = 3，即 4.next = 3。
- 3.next = None。链表变为：5 -> 4 -> 3。
依此类推，最终链表变为：5 -> 4 -> 3 -> 2 -> 1。

时空复杂度

时间复杂度: O(n)，其中 n 是链表的长度。递归会遍历链表中的每个节点一次。
空间复杂度: O(n)，递归调用栈的深度与链表长度成正比。

易错点

递归终止条件：必须判断 if not head or not head.next，否则会导致空指针异常或无限递归。
链表成环：在反转指针后，一定要将当前节点的 next 置为 None，否则链表会成环。
返回值的理解：返回值是反转后的新链表的头节点（即原链表的最后一个节点），而不是当前节点。

数组中的第K个最大元素

215. 数组中的第K个最大元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

方法1：快速选择

快速选择算法：通过选择一个基准值（pivot），将数组分为两部分，左边部分的元素都大于等于基准值，右边部分的元素都小于等于基准值。然后根据 k 的值决定在哪个分区继续查找。
分区操作：使用双指针法进行分区操作，确保左边分区的元素都大于等于基准值，右边分区的元素都小于等于基准值。
递归调用：根据 k 的值决定在左边分区还是右边分区继续查找，直到找到第 k 大的元素。

 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
29
30
31
32
33
34
35
36
37
38
39
40


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # 定义快速选择函数
        def quickSelect(left, right, k) -> int:
            
            # 如果区间只有一个元素，直接返回该元素
            if left == right:
                return nums[left]
            
            # 选择数组中间位置的元素作为基准值（pivot）
            pivot = nums[(left+right)//2]
            i, j = left, right 
            
            # 使用双指针进行分区操作
            while True:
                # 从左向右找到第一个小于等于 pivot 的元素
                while nums[i] > pivot:
                    i += 1
                # 从右向左找到第一个大于等于 pivot 的元素
                while nums[j] < pivot:
                    j -= 1
                # 如果指针相遇或交叉，结束循环
                if i >= j:
                    break 
                # 交换两个元素的位置
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
            
            # 计算左边分区的元素数量
            cnt = j - left + 1
            # 如果 k 小于等于左边分区的元素数量，则在左边分区继续查找
            if k <= cnt:
                return quickSelect(left, j, k)
            # 否则在右边分区继续查找，同时更新 k 的值
            else:
                return quickSelect(j+1, right, k-cnt)

        # 调用快速选择函数，返回第 k 大的元素
        return quickSelect(0, len(nums)-1, k)

时间复杂度分析

平均情况：O(n)，其中 n 是数组的长度。快速选择算法在平均情况下每次能将问题规模减半，因此时间复杂度为线性。
最坏情况：O(n^2)，如果每次选择的基准值都是最小或最大值，导致每次分区只能减少一个元素。

空间复杂度分析

空间复杂度：O(1)，除了递归调用栈外，算法没有使用额外的空间。

易错点

是严格小于，而不是小于等于：会影响分区结果。如果全是pivot，这会让指针越界
分区（Partition）：将数组分为两部分：
- 左侧部分：所有元素小于基准值。
- 右侧部分：所有元素大于基准值。
- 基准值本身位于正确的位置。
cnt和k：
- k是从1开始计数的，不要弄错
- k大于cnt意味着前面没罩住，往后找
- k小于等于cnt意味着结果在前面，缩小尾巴

方法2：最大堆

最大堆是一种树形数据结构，其中每个节点的值都大于或等于其子节点的值。我们可以通过构建一个最大堆来找到第k个最大元素。具体步骤如下：

构建最大堆：将整个数组构建成一个最大堆。
移除堆顶元素：从堆中移除堆顶元素（最大值），重复k-1次。
返回堆顶元素：最后堆顶的元素就是第k个最大的元素。

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


class Heap:
    def __init__(self, arr=[]):
        self.heap = arr
        if len(arr) > 0:
            for i in range(len(arr)//2-1, -1, -1):
                self.heapify_down(i)
    
    def parent(self, i):
        return (i-1)//2
    
    def left_son(self, i):
        return 2*i+1
    
    def right_son(self, i):
        return 2*i+2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def size(self):
        return len(self.heap)
    
    def heapify_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def heapify_down(self, i):
        index = i 
        left = self.left_son(i)
        right = self.right_son(i)

        if left < self.size() and self.heap[left] > self.heap[index]:
            index = left 
        if right < self.size() and self.heap[right] > self.heap[index]:
            index = right 

        if index != i:
            self.swap(index, i)
            self.heapify_down(index)
    
    def push(self, num):
        self.heap.append(num)
        self.heapify_up(self.size()-1)

    def pop(self):
        res = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return res 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = Heap(nums)
        for i in range(k-1):
            heap.pop()
        return heap.pop()

时间复杂度分析

返回堆顶元素的时间复杂度为 O(1)

每次移除堆顶元素的时间复杂度为 O(log n)

从空堆逐个插入建堆：
- 每次插入的时间复杂度是 O(log n)。
- 总时间复杂度是 O(n log n)。
从数组自下而上建堆：
- 使用 heapify_down 操作，总时间复杂度是 O(n)。

为啥从下而上建堆是`O(n)`

常见误解：
- 通常我们会认为建堆的时间复杂度是 O(n log n)，因为每个元素插入堆的时间是 O(log n)，总共有 n 个元素，所以总的复杂度是 O(n log n)。
- 但实际上，建堆的时间复杂度是 O(n)，而不是 O(n log n)。
为什么是 O(n)：
- 在常规的从空堆插入元素的情况下，每次插入需要 O(log n)，所以总复杂度是 O(n log n)。
- 但是，当我们从一个已有的数组（arr）构建堆时，采用的是自下而上的 heapify 操作，而不是从空堆逐个插入。
- 具体来说，建堆的过程是从数组的中间位置开始（即从 n//2 - 1 到 0），对每个节点进行 heapify_down 操作。
- heapify_down 的时间复杂度取决于当前节点的高度，而不是树的高度。对于第 i 层的节点，heapify_down 的时间复杂度是 O(h-i)，其中 h 是树的高度。
- 通过数学计算，可以发现建堆的总时间复杂度是 O(n)。
数学证明
- 假设树的高度为 h，第 i 层有 2^i 个节点，每个节点的 heapify_down 操作的时间复杂度为 O(h-i)。
- 总时间复杂度的计算如下： $$ T(n) = \sum_{i=0}^{h} 2^i \cdot (h - i) $$
- 这个求和结果可以证明是 O(n)

空间复杂度分析

构建堆需要额外的空间来存储堆结构，空间复杂度为 O(n)。

易错点

堆的构建：在初始化堆时，需要从数组的中间位置开始进行 heapify_down 操作，而不是从头开始，这会影响建堆的复杂度，从O(nlogn)降低到O(n)
堆的维护：在 pop 操作后，需要正确地维护堆的性质，即调用 heapify_down。
边界条件：当 k=1 时，直接返回堆顶元素即可，不需要进行移除操作。

K 个一组翻转链表

25. K 个一组翻转链表

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

方法：双指针翻转

统计链表长度：首先统计链表的长度，确定需要翻转的组数。
分组翻转：对每一组的 k 个节点进行翻转，翻转过程中需要维护前驱节点和当前节点的关系。
更新指针：翻转完一组后，更新前驱节点和当前节点，继续处理下一组节点。
返回结果：最终返回修改后的链表。

 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 Solution:  
    def reverseKGroup(self, head, k) -> Optional[ListNode]:  
        # 初始化计数器 cnt、当前节点 cur 和虚拟头节点 dummy  
        cnt, cur, dummy = 0, head, ListNode(-1, head)   
        
        # 统计链表长度  
        while cur is not None:  
            cnt, cur = cnt+1, cur.next   
        
        # 计算需要翻转的组数  
        n = cnt // k   
        
        # 初始化前驱节点 prv 和当前节点 cur  
        prv, cur =  dummy, head   
        
        # 遍历每一组节点进行翻转  
        for _ in range(n):  
            # 每组需要翻转 k-1 次  
            for _ in range(k - 1):  
                nxt = cur.next  # 保存当前节点的下一个节点  
                cur.next = nxt.next  # 当前节点指向下下个节点  
                nxt.next = prv.next  # 下一个节点指向当前组的新头节点  
                prv.next = nxt  # 前驱节点指向新的头节点  
            # 更新前驱节点和当前节点到下一组  
            prv, cur = cur, cur.next  
​  
        # 返回修改后的链表  
        return dummy.next

复杂度分析

时间复杂度：
- 统计链表长度：O(n)，其中 n 是链表长度。
- 翻转链表组：外层循环遍历 n//k 组，每组需要翻转 k 个节点，时间复杂度为 O(n)。
- 总时间复杂度为 O(n)。
空间复杂度：
- 只使用了常数级别的额外空间（几个指针），空间复杂度为 O(1)。

三数之和

15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0。请你找出所有和为 0 且不重复的三元组。

方法1：排序 + 双指针

排序：首先将数组排序，这样可以利用双指针的技巧来减少时间复杂度。
固定一个数：遍历数组，固定一个数 nums[i]，然后使用双指针在剩下的数组中寻找其他两个数，使得这三个数的和为 0。
双指针：使用两个指针 j 和 k，分别指向 i+1 和 len(nums)-1。根据三数之和与 0 的关系，移动指针来逼近目标。
去重：为了避免重复的三元组，需要跳过相同的元素

 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
29
30
31
32
33


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 首先对数组进行排序
        res = []  # 用于存储结果的三元组
      
        # 遍历数组，固定一个数
        for i in range(0, len(nums)-2):
            # 如果当前数和前一个数相同，跳过以避免重复
            if i > 0 and nums[i] == nums[i-1]:
                continue
              
            j, k = i+1, len(nums)-1  # 初始化双指针
            while j < k:
                total = nums[i] + nums[j] + nums[k]  # 计算三数之和
              
                if total == 0:
                    # 如果和为0，加入到结果中
                    res.append([nums[i], nums[j], nums[k]])
                    # 跳过重复的元素
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    # 移动双指针
                    j, k = j+1, k-1
                elif total > 0:
                    # 如果和大于0，移动右指针
                    k -= 1
                else:
                    # 如果和小于0，移动左指针
                    j += 1
      
        return res  # 返回结果

时间复杂度分析

排序：O(n log n)，其中 n 是数组的长度。排序是算法中最耗时的部分。
双指针遍历：O(n^2)，外层循环遍历每个元素，内层循环使用双指针遍历剩余的元素。
总时间复杂度：O(n log n + n^2)，在大多数情况下，O(n^2) 是主要部分。

空间复杂度分析

排序：O(log n)，排序算法的空间复杂度。
结果存储：O(n)，最坏情况下需要存储 O(n) 个三元组。
总空间复杂度：O(n)，主要用于存储结果。

易错点

去重：在固定一个数和移动指针时，必须跳过相同的元素，否则会导致重复的三元组。
边界条件：在处理数组边界时，确保索引不会越界。
排序：在开始双指针之前，必须对数组进行排序，否则无法保证双指针的有效性。

最大子数组和

53. 最大子数组和

题目描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

方法：动态规划（Kadane’s Algorithm）

核心思路：
- 状态定义：cur_sum 表示以当前元素结尾的子数组的最大和。
- 状态转移：对于每个元素，我们有两个选择：要么将其加入到当前子数组中，要么以当前元素为起点重新开始一个新的子数组。我们选择两者中较大的一个，即 cur_sum = max(cur_sum + num, num)。
- 边界条件：初始时，cur_sum 和 max_sum 都设置为负无穷大，以确保数组中的任何元素都能成为新的起点。
- 最终结果：在整个遍历过程中，我们始终维护一个 max_sum，它记录了到目前为止的最大子数组和。
算法步骤：
- 初始化 cur_sum 和 max_sum 为 -float('inf')。
- 遍历数组中的每个元素：
  - 更新 cur_sum 为 max(cur_sum + num, num)。
  - 更新 max_sum 为 max(max_sum, cur_sum)。
- 返回 max_sum。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 初始化当前子数组和与最大子数组和
        cur_sum, max_sum = -float('inf'), -float('inf')
        # 遍历数组中的每个元素
        for num in nums:
            # 更新当前子数组和，选择加入当前元素或重新开始
            cur_sum = max(cur_sum + num, num)
            # 更新最大子数组和
            max_sum = max(max_sum, cur_sum)
        # 返回最大子数组和
        return max_sum

时间复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只需遍历一次数组，每个元素的操作都是常数时间。
空间复杂度：O(1)，只使用了常数个额外空间来存储 cur_sum 和 max_sum。

易错点

初始化值：cur_sum 和 max_sum 应初始化为 -float('inf')，而不是 0，因为数组可能包含负数，我们需要确保任何单个元素都能成为起点。
状态转移：在更新 cur_sum 时，一定要选择 max(cur_sum + num, num)，而不是直接加上当前元素，否则可能会错过更优的子数组。

快速排序

912. 排序数组

题目描述

这是一道快速排序的经典实现题目。给定一个整数数组 nums，要求将数组升序排序。

方法：快速排序

核心思路：
- 分治法：快速排序是一种基于分治法的排序算法。它的基本思想是通过选择一个基准值（pivot），将数组分为两部分：一部分小于等于基准值，另一部分大于等于基准值。
- 递归排序：对每一部分递归地进行快速排序，最终实现整个数组的排序。
- 基准值选择：通常选择数组中间位置的元素作为基准值，这样可以避免最坏情况（如已排序数组）的发生。
- 分区操作：使用双指针法进行分区操作，确保左边分区的元素都小于等于基准值，右边分区的元素都大于等于基准值。
算法步骤：
- 终止条件：如果 left >= right，当前数组已经有序，直接返回。
- 基准值选择：选择数组中间位置的元素作为基准值（pivot）。
- 分区操作：使用双指针 i 和 j 进行分区操作：
  - 从左向右找到第一个大于等于 pivot 的元素。
  - 从右向左找到第一个小于等于 pivot 的元素。
  - 如果 i >= j，分区结束。
  - 否则，交换 nums[i] 和 nums[j]，并移动指针。
- 递归排序：对左右两部分分别进行递归排序。

 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
29
30
31
32
33
34
35
36


class Solution:
    def quickSort(self, nums, left, right):
        # 终止条件：如果区间长度小于等于 1，直接返回
        if left >= right:
            return 
      
        # 选择基准值：数组中间位置的元素
        pivot = nums[(left + right) // 2]
        i, j = left, right
      
        # 分区操作
        while True:
            # 从左向右找到第一个大于等于 pivot 的元素
            while nums[i] < pivot:
                i += 1
            # 从右向左找到第一个小于等于 pivot 的元素
            while nums[j] > pivot:
                j -= 1
            # 如果指针相遇或交叉，结束分区
            if i >= j:
                break
            # 交换两个元素的位置
            nums[i], nums[j] = nums[j], nums[i]
            # 移动指针
            i, j = i + 1, j - 1
      
        # 递归排序左半部分
        self.quickSort(nums, left, j)
        # 递归排序右半部分
        self.quickSort(nums, j + 1, right)

    def sortArray(self, nums: List[int]) -> List[int]:
        # 调用快速排序函数，对整个数组进行排序
        self.quickSort(nums, 0, len(nums) - 1)
        # 返回排序后的数组
        return nums

时间复杂度分析

平均情况：O(n log n)，其中 n 是数组的长度。快速排序每次将数组分为两部分，理想情况下每次分区都能将问题规模减半。
最坏情况：O(n^2)，如果每次选择的基准值都是最小或最大值，导致每次分区只能减少一个元素。

空间复杂度分析

空间复杂度：O(log n)，主要用于递归调用栈，最坏情况下可能需要 O(n) 的空间。

易错点

基准值选择：
- 如果选择的基准值不平衡（如最小或最大值），可能导致算法效率下降。
- 选择数组中间位置的元素作为基准值可以尽量避免这种情况。
分区操作：
- 在分区操作中，确保指针的正确移动和元素交换，否则可能导致分区失败。
- 注意指针移动时要检查边界条件，防止越界。
递归终止条件：
- 确保递归终止条件正确，否则可能导致无限递归。
指针移动：
- 在交换元素后，记得更新指针的位置，否则可能导致死循环。

变体

三路快速排序：
- 对于含有大量重复元素的数组，可以将数组分为三部分：小于 pivot 的部分、等于 pivot 的部分和大于 pivot 的部分。
- 这种方法可以避免重复元素的重复比较。
随机化选择基准值：
- 在每次分区时随机选择一个元素作为基准值，从而避免最坏情况的发生。
小数组使用插入排序：
- 当数组长度较小时（如 n <= 16），使用插入排序代替快速排序，因为插入排序在小数组上表现更好。

合并两个有序链表

21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

方法：双指针

这道题的核心思路是通过双指针遍历两个链表，比较两个链表当前节点的值，将较小的节点连接到新链表中，直到其中一个链表遍历结束。然后将未遍历完的链表直接连接到新链表的末尾。

 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
29
30
31


class Solution:
    def mergeTwoLists(self, list1, list2) -> Optional[ListNode]:
        # 创建一个虚拟节点，作为新链表的头节点前驱
        dummy = ListNode()
        # 创建一个指针 cur，指向新链表的当前节点
        cur = dummy
      
        # 当两个链表都未遍历完时，进行比较
        while list1 and list2:
            if list1.val < list2.val:
                # 如果 list1 的当前节点值较小，将其连接到新链表中
                cur.next = list1
                # 移动 list1 的指针到下一个节点
                list1 = list1.next 
            else:
                # 如果 list2 的当前节点值较小或相等，将其连接到新链表中
                cur.next = list2
                # 移动 list2 的指针到下一个节点
                list2 = list2.next 
            # 移动 cur 指针到新链表的最后一个节点
            cur = cur.next 
      
        # 如果 list1 还有剩余节点，将其连接到新链表的末尾
        if list1:
            cur.next = list1
        # 如果 list2 还有剩余节点，将其连接到新链表的末尾
        if list2:
            cur.next = list2
      
        # 返回新链表的头节点（dummy.next）
        return dummy.next

时空复杂度分析

时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的所有节点。
空间复杂度：O(1)，除了分配一个虚拟节点外，没有使用额外的空间。

易错点

虚拟节点的使用：使用虚拟节点可以简化链表的操作，避免处理空链表的特殊情况。
指针的移动：在每次连接节点后，别忘了移动 cur 指针到新链表的最后一个节点。
剩余节点的处理：在遍历结束后，一定要将未遍历完的链表直接连接到新链表的末尾，不要遗漏。

变体

合并 K 个有序链表：可以使用分治法或最小堆来解决。分治法的时间复杂度为 O(kn log k)，其中 k 是链表的数量，n 是每个链表的平均长度。
合并两个有序链表并去重：在合并时，如果当前节点的值与下一个节点的值相同，则跳过重复的节点。

最长回文子串

5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

方法1：中心扩展法

核心思路

回文子串的特点是从中心向两边扩展时，左右字符对称。因此，我们可以遍历字符串，以每个字符为中心，分别考虑奇数长度和偶数长度的回文子串，不断向两边扩展，找到最长的回文子串。

代码实现

 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


class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 定义中心扩展函数
        def expandAroundCenter(left, right) -> str:
            # 当左右指针在边界内且字符相等时，继续扩展
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 返回当前找到的回文子串
            return s[left+1:right]

        # 初始化最长回文子串为空字符串
        longest = ""
        # 遍历字符串中的每个字符
        for i in range(len(s)):
            # 以当前字符为中心，考虑奇数长度的回文子串
            odd = expandAroundCenter(i, i)
            # 以当前字符和下一个字符为中心，考虑偶数长度的回文子串
            even = expandAroundCenter(i, i+1)
            # 更新最长回文子串
            if len(odd) > len(longest):
                longest = odd
            if len(even) > len(longest):
                longest = even
      
        # 返回最长回文子串
        return longest

时间复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串的长度。对于每个字符，我们都需要向两边扩展，最坏情况下需要扩展整个字符串。
空间复杂度：O(1)，除了存储结果外，算法没有使用额外的空间。

易错点

边界条件：在扩展时，要确保左右指针不超出字符串的边界。
奇数和偶数长度的回文子串：需要同时考虑以当前字符为中心的回文子串（奇数长度）和以当前字符及下一个字符为中心的回文子串（偶数长度）。

方法2：动态规划

核心思路

使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文子串。根据回文子串的性质，如果 s[i] == s[j] 且 dp[i+1][j-1] 是回文子串，那么 dp[i][j] 也是回文子串。

代码实现

 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
29


class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # 初始化 dp 数组
        dp = [[False] * n for _ in range(n)]
        longest = ""

        # 所有长度为 1 的子串都是回文子串
        for i in range(n):
            dp[i][i] = True
            longest = s[i]

        # 检查长度为 2 的子串
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                longest = s[i:i+2]

        # 检查长度大于 2 的子串
        for length in range(3, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > len(longest):
                        longest = s[i:j+1]

        # 返回最长回文子串
        return longest

时间复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串的长度。我们需要填充一个 n x n 的二维数组。
空间复杂度：O(n^2)，用于存储动态规划表。

易错点

初始化：所有长度为 1 的子串都是回文子串，长度为 2 的子串需要单独检查。
状态转移方程：只有在 s[i] == s[j] 且 dp[i+1][j-1] 是回文子串时，dp[i][j] 才是回文子串。

变体

最长回文子序列：与最长回文子串不同，子序列可以不连续。可以使用动态规划来解决，时间复杂度为 O(n^2)。
计算所有回文子串的数量：可以使用中心扩展法或动态规划来解决，时间复杂度为 O(n^2)。

无重复字符的最长子串

题目描述

方案一：双指针+哈希集合

方案二：双指针 + 哈希映射

时空复杂度分析

LRU缓存

题目描述

方案：哈希表+双向链表

时空复杂度分析

易错点

反转链表

题目描述

方法一：当前不动，后移动到前

时空复杂度

易错点

方法二：递归法

举例说明

时空复杂度

易错点

数组中的第K个最大元素

题目描述

方法1：快速选择

时间复杂度分析

空间复杂度分析

易错点

方法2：最大堆

时间复杂度分析

为啥从下而上建堆是O(n)

空间复杂度分析

易错点

K 个一组翻转链表

题目描述

方法：双指针翻转

复杂度分析

三数之和

题目描述

方法1：排序 + 双指针

时间复杂度分析

空间复杂度分析

易错点

最大子数组和

题目描述

方法：动态规划（Kadane’s Algorithm）

时间复杂度分析

易错点

快速排序

题目描述

方法：快速排序

时间复杂度分析

空间复杂度分析

易错点

变体

合并两个有序链表

题目描述

方法：双指针

时空复杂度分析

易错点

变体

最长回文子串

题目描述

方法1：中心扩展法

核心思路

代码实现

时间复杂度分析

易错点

方法2：动态规划

核心思路

代码实现

时间复杂度分析

易错点

变体

为啥从下而上建堆是`O(n)`