# 常见算法模式

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

---

## 模式 1：双指针

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

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

**示例问题**：
- 两数之和（有序数组）
- 验证回文串
- 盛最多水的容器
- 三数之和

**实现（Python）**：
```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）**：
```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）—— 固定窗口**：
```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）—— 可变窗口**：
```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）**：
```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）**：
```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）**：
```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）**：
```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）**：
```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）**：
```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）**：
```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）**：
```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）**：
```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：二分查找

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

**何时使用**：
- 在有序数组中查找
- 查找第一个/最后一个出现位置
- 在旋转有序数组中查找
- 寻找峰值元素
- 在二维矩阵中查找

**模板**：
```python
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）**：
```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）**：
```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 背包

**模板（记忆化）**：
```python
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：动态规划（自底向上）

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

**模板（表格法）**：
```python
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]
```

**空间优化**（以斐波那契为例）：
```python
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
- 动态规划 + 记忆化
- 回溯 + 剪枝