wehub/skillhub-117-code-mentor
1
0
Fork 0
Code Issues Pull Requests Actions Deployments Models Agent Notes Packages Projects Releases Wiki Activity
Files
main
skillhub-117-code-mentor/references/algorithms/common-patterns.md
T
wehub-skill-sync 6eb137bec1 chore: import zh skill code-mentor
2026-07-13 21:36:32 +08:00

16 KiB
Raw Permalink Blame History

常见算法模式

本参考涵盖编程面试和实际解决问题中最常用的算法模式。理解这些模式有助于你识别应对陌生问题时应采用哪种方法。

模式 1：双指针

适用场景：需要寻找数对、三元组或从两端处理元素的数组或字符串问题。

何时使用：

  • 在有序数组中寻找和为目标的数对
  • 原地反转数组或字符串
  • 从有序数组中移除重复项
  • 盛最多水的容器类问题

示例问题：

  • 两数之和（有序数组）
  • 验证回文串
  • 盛最多水的容器
  • 三数之和

实现（Python）：

def two_sum_sorted(arr, target):
    """在有序数组中寻找两个数使其和等于目标值。"""
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # 需要更大的和
        else:
            right -= 1  # 需要更小的和

    return None  # 未找到解

实现（JavaScript）：

function twoSumSorted(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left < right) {
        const currentSum = arr[left] + arr[right];

        if (currentSum === target) {
            return [left, right];
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }

    return null;
}

时间复杂度：O(n) —— 单次遍历数组 空间复杂度：O(1) —— 仅两个指针

模式 2：滑动窗口

适用场景：涉及子数组或子串的问题，需要寻找最优窗口大小或跟踪连续序列中的元素。

何时使用：

  • 大小为 k 的最大/最小子数组和
  • 无重复字符的最长子串
  • 在字符串中查找所有字母异位词
  • 最小覆盖子串

类型：

  1. 固定大小窗口：窗口大小恒定（例如大小为 k 的最大和）
  2. 可变大小窗口：窗口根据条件增大或缩小

示例问题：

  • 大小为 K 的最大子数组和
  • 无重复字符的最长子串
  • 最小覆盖子串
  • 字符串中的排列

实现（Python）—— 固定窗口：

def max_sum_subarray(arr, k):
    """找出大小为 k 的任意子数组的最大和。"""
    if len(arr) < k:
        return None

    # 计算第一个窗口的和
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # 滑动窗口
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)

    return max_sum

实现（JavaScript）—— 可变窗口：

function lengthOfLongestSubstring(s) {
    const seen = new Set();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        // 收缩窗口直到无重复
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }

        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

时间复杂度：O(n) —— 每个元素最多被访问两次 空间复杂度：固定窗口为 O(k)，可变窗口（含哈希集合）为 O(n)

模式 3：快慢指针（Floyd 环检测）

适用场景：链表问题，尤其是环检测和寻找中间元素。

何时使用：

  • 检测链表中的环
  • 寻找链表的中点
  • 寻找环的起点
  • 判断一个数是否为快乐数

示例问题：

  • 环形链表
  • 快乐数
  • 寻找链表的中间节点
  • 环起点检测

实现（Python）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    """检测链表是否有环。"""
    if not head:
        return False

    slow = fast = head

    while fast and fast.next:
        slow = slow.next        # 移动 1 步
        fast = fast.next.next   # 移动 2 步

        if slow == fast:
            return True  # 检测到环

    return False

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

模式 4：合并区间

适用场景：处理重叠区间、调度或范围的问题。

何时使用：

  • 合并重叠区间
  • 插入区间
  • 会议室问题
  • 区间交集

示例问题：

  • 合并区间
  • 插入区间
  • 会议室 II
  • 区间列表的交集

实现（Python）：

def merge_intervals(intervals):
    """合并重叠区间。"""
    if not intervals:
        return []

    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for current in intervals[1:]:
        last_merged = merged[-1]

        if current[0] <= last_merged[1]:
            # 重叠 —— 合并
            merged[-1] = [last_merged[0], max(last_merged[1], current[1])]
        else:
            # 不重叠 —— 添加新区间
            merged.append(current)

    return merged

时间复杂度：O(n log n) —— 因排序导致 空间复杂度：O(n) —— 输出空间

模式 5：循环排序

适用场景：数组中包含给定范围内（通常为 1 到 n）的数字的问题。

何时使用：

  • 查找缺失/重复的数字
  • 查找所有缺失的数字
  • 查找损坏数对
  • 包含 1 到 n 数字的数组

示例问题：

  • 寻找缺失数字
  • 寻找所有缺失数字
  • 寻找重复数字
  • 寻找损坏数对

实现（Python）：

def cyclic_sort(nums):
    """对范围为 1 到 n 的数组进行排序。"""
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1

        if nums[i] != nums[correct_index]:
            # 交换到正确位置
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1

    return nums

def find_missing_number(nums):
    """在 [0, n] 范围内查找缺失的数字。"""
    n = len(nums)
    i = 0

    # 循环排序
    while i < n:
        correct_index = nums[i]
        if nums[i] < n and nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1

    # 查找缺失
    for i in range(n):
        if nums[i] != i:
            return i

    return n

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

模式 6：链表原地反转

适用场景：在不使用额外空间的情况下反转链表或链表的一部分。

何时使用：

  • 反转整个链表
  • 反转从位置 m 到 n 的子链表
  • 按 k 个一组反转
  • 回文链表检测

示例问题：

  • 反转链表
  • 反转链表 II
  • K 个一组翻转链表

实现（Python）：

def reverse_linked_list(head):
    """原地反转链表。"""
    prev = None
    current = head

    while current:
        next_node = current.next  # 保存下一个节点
        current.next = prev       # 反转指针
        prev = current            # 向前移动 prev
        current = next_node       # 向前移动 current

    return prev  # 新的头节点

实现（JavaScript）：

function reverseLinkedList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        const nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

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

模式 7：树 BFS（广度优先搜索）

适用场景：树的层序遍历，查找层级特定信息。

何时使用：

  • 层序遍历
  • 查找最小深度
  • 锯齿形层序遍历
  • 连接层序兄弟节点
  • 树的右视图

示例问题：

  • 二叉树的层序遍历
  • 二叉树的锯齿形遍历
  • 二叉树的最小深度
  • 连接层序兄弟节点

实现（Python）：

from collections import deque

def level_order_traversal(root):
    """BFS 遍历，返回层级列表。"""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

时间复杂度：O(n) 空间复杂度：O(n) —— 队列空间

模式 8：树 DFS（深度优先搜索）

适用场景：基于路径的树问题，递归树遍历。

何时使用：

  • 查找从根到叶的所有路径
  • 路径数字之和
  • 给定和的路径
  • 统计和为某值的路径数
  • 树的直径

类型：

  1. 前序遍历：根 → 左 → 右
  2. 中序遍历：左 → 根 → 右
  3. 后序遍历：左 → 右 → 根

示例问题：

  • 二叉树路径
  • 路径总和
  • 求根到叶节点数字之和
  • 二叉树的直径

实现（Python）：

def has_path_sum(root, target_sum):
    """检查树是否存在根到叶路径，其节点和等于给定值。"""
    if not root:
        return False

    # 叶节点 —— 检查和是否匹配
    if not root.left and not root.right:
        return root.val == target_sum

    # 递归 DFS
    remaining_sum = target_sum - root.val
    return (has_path_sum(root.left, remaining_sum) or
            has_path_sum(root.right, remaining_sum))

时间复杂度：O(n) 空间复杂度：O(h)，其中 h 为树高（递归栈）

模式 9：双堆

适用场景：需要查找中位数或将元素分为两半的问题。

何时使用：

  • 从数据流中找中位数
  • 滑动窗口中位数
  • IPO（最大化资本）

结构：

  • 最大堆：存储较小的一半数字
  • 最小堆：存储较大的一半数字
  • 中位数为最大堆的最大值或两堆堆顶的平均值

实现（Python）：

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # 较小的一半（取反实现最大堆）
        self.min_heap = []  # 较大的一半

    def add_num(self, num):
        # 先加入最大堆
        heapq.heappush(self.max_heap, -num)

        # 平衡：将最大堆的最大值移到最小堆
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        # 确保最大堆元素个数等于或多于最小堆
        if len(self.max_heap) < len(self.min_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2

时间复杂度：插入 O(log n)，查找中位数 O(1) 空间复杂度：O(n)

模式 10：子集（回溯）

适用场景：需要生成所有组合、排列或子集的问题。

何时使用：

  • 生成所有子集/幂集
  • 排列
  • 组合
  • 字母大小写全排列

示例问题：

  • 子集
  • 排列
  • 组合
  • 括号生成

实现（Python）：

def subsets(nums):
    """使用回溯生成所有子集。"""
    result = []

    def backtrack(start, current):
        # 添加当前子集
        result.append(current[:])

        # 探索后续元素
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()  # 回溯

    backtrack(0, [])
    return result

时间复杂度：O(2^n) —— 指数级 空间复杂度：O(n) —— 递归深度

模式 11：二分查找

适用场景：在有序数组或搜索空间中查找，寻找边界。

何时使用：

  • 在有序数组中查找
  • 查找第一个/最后一个出现位置
  • 在旋转有序数组中查找
  • 寻找峰值元素
  • 在二维矩阵中查找

模板：

def binary_search(arr, target):
    """标准二分查找。"""
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 避免溢出

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 未找到

时间复杂度：O(log n) 空间复杂度：O(1)

模式 12：Top K 元素

适用场景：查找 k 个最大/最小元素，k 个最频繁元素。

何时使用：

  • K 个最大/最小元素
  • K 个最近的点
  • K 个最频繁的元素
  • 按频率对字符排序

实现（Python）：

import heapq

def k_largest_elements(nums, k):
    """使用最小堆查找 k 个最大元素。"""
    # 维护大小为 k 的最小堆
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return min_heap

时间复杂度：O(n log k) 空间复杂度：O(k)

模式 13：改进版二分查找

适用场景：针对复杂场景的二分查找变体。

何时使用：

  • 在旋转有序数组中查找
  • 在旋转有序数组中查找最小值
  • 在无限有序数组中查找
  • 查找范围（第一个和最后一个位置）

实现（Python）：

def search_rotated_array(nums, target):
    """在旋转有序数组中查找目标值。"""
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # 判断哪一半是有序的
        if nums[left] <= nums[mid]:  # 左半有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

模式 14：动态规划（自顶向下）

适用场景：具有重叠子问题的最优化问题。

何时使用：

  • 斐波那契数列、爬楼梯
  • 打家劫舍
  • 零钱兑换
  • 最长公共子序列
  • 0/1 背包

模板（记忆化）：

def fibonacci(n, memo={}):
    """使用记忆化计算第 n 个斐波那契数。"""
    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

时间复杂度：取决于具体问题（通常为 O(n) 或 O(n²)） 空间复杂度：O(n) —— 记忆化加递归栈

模式 15：动态规划（自底向上）

适用场景：与自顶向下相同，但采用迭代方式（通常更高效）。

模板（表格法）：

def fibonacci_dp(n):
    """使用自底向上 DP 计算第 n 个斐波那契数。"""
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

空间优化（以斐波那契为例）：

def fibonacci_optimized(n):
    """空间优化的斐波那契计算。"""
    if n <= 1:
        return n

    prev2, prev1 = 0, 1

    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

如何选择正确的模式

问自己以下几个问题：

  1. 输入结构是什么？

    • 有序数组 → 二分查找、双指针
    • 链表 → 快慢指针、原地反转
    • 树 → BFS、DFS
    • 区间 → 合并区间

  2. 我在寻找什么？

    • 子数组/子串 → 滑动窗口
    • 数对/三元组 → 双指针
    • 所有组合 → 回溯
    • 带选择的最优解 → 动态规划
    • Top k 个元素 → 堆

  3. 是否存在约束条件？

    • 数字范围在 [1, n] → 循环排序
    • 需要中位数 → 双堆
    • 原地修改 → 双指针、循环排序

  4. 时间复杂度要求是什么？

    • O(log n) → 二分查找
    • O(n) → 双指针、滑动窗口、哈希表
    • O(n log n) → 排序、堆
    • 可以接受指数级？ → 回溯、递归

练习策略：

  1. 每次掌握一种模式
  2. 每个模式解决 5-10 道题
  3. 在新问题中识别模式
  4. 组合模式解决复杂问题

常见模式组合：

  • 双指针 + 滑动窗口
  • 二分查找 + DFS
  • 动态规划 + 记忆化
  • 回溯 + 剪枝
Reference in New Issue View Git Blame Copy Permalink