【算法】算法题核心类别与通用解题思路

以下系统地汇总了算法题的主要类别，并为每一类提供了通用的解题思路和技巧。

算法题核心类别与通用解题思路

算法题虽然千变万化，但绝大多数都可以归入以下几类。掌握每一类的“解题模板”和核心思想，就能做到举一反三。

1. 数据结构类 (Data Structures)

这类问题直接考察对基础数据结构的应用和理解。

• 数组 & 字符串 (Array & String)

  • 核心思想： 在连续内存空间上进行操作。常用技巧是使用指针（下标）来遍历或标记位置。
  • 通用思路：
    • 双指针 (Two Pointers)： 解决有序数组、去重、合并、滑动窗口等问题。
      • 对撞指针： 一前一后向中间遍历，用于“两数之和”、“反转字符串”等。
      • 快慢指针： 一快一慢，用于“判断循环”、“找中点”、“删除元素”等。
    • 滑动窗口 (Sliding Window)： 解决子串/子数组问题（如“找和为K的最短子数组”、“最长无重复字符子串”）。
      • 模板： 用 left 和 right 指针维护一个窗口，right 向右扩张，left 根据条件向右收缩，并在此过程中更新答案。
    • 前缀和 (Prefix Sum)： 快速求解任意区间和。
      • 模板： 预处理一个 prefix[i] 数组，存储 nums[0] 到 nums[i-1] 的和，则区间 [i, j] 的和为 prefix[j+1] - prefix[i]。

• 链表 (Linked List)

  • 核心思想： 指针操作是核心。注意处理头节点和边界条件（空链表、单节点链表）。
  • 通用思路：
    • 虚拟头节点 (Dummy Node)： 在任何可能修改头节点的操作前，创建一个 dummy 节点指向 head，可以简