1. 双指针（Two Pointer）
适用场景：
- 数组或字符串问题，特别是在有序的情况下。
- 在求解一些与区间、子数组、子序列相关的问题时，双指针非常有用。
典型问题：
- 有序数组的两数之和：在有序数组中找出两个数的和等于某个目标值。
- 回文字符串检查：判断一个字符串是否是回文。
- 滑动窗口问题：维护一个动态的子数组/子串窗口。
思路：
- 双指针法通过维护两个指针（一个指向数组的起始位置，另一个指向结束位置），逐步进行遍历和条件判断。可以用来减少暴力解法中的重复计算。
常见变种：
- 快慢指针：常用于链表问题，比如 检测链表是否有环（快指针每次走两步，慢指针走一步）。
- 左右指针：从数组两端向中间逼近，常用于排序、搜索等问题。
2. 滑动窗口（Sliding Window）
适用场景：
- 用于求解数组、字符串中某些满足条件的子区间（例如最大子数组和、最小覆盖子串等）。
- 需要动态维护窗口内元素的属性。
典型问题：
- 最小覆盖子串：找出字符串中最小的包含某些字符的子串。
- 最长无重复子串：在字符串中找到没有重复字符的最长子串。
- 最大连续子数组和：求解在某区间内和最大的子数组。
思路：
- 通过维护一个窗口（可以是一个数组或哈希表）动态扩展和收缩，来找到符合条件的最优解。通常可以通过两个指针（
left和right）来控制窗口的范围。
3. 分治法（Divide and Conquer）
适用场景：
- 当问题可以被拆解成多个子问题时，使用分治法非常有效。
- 适合递归问题，尤其是可以利用 合并（Merge） 或 拆分（Split） 操作的场景。
典型问题：
- 归并排序：将一个大的数组分成若干小部分，递归排序后合并。
- 快速排序：通过选择一个基准元素，将数组分成两个部分，分别递归处理。
- 二分查找：通过递归或迭代不断将数组分成两半来找到目标元素。
思路：
- 将一个大问题分解为若干小问题，分别求解小问题后再合并结果。分治法通常基于递归实现。
4. 动态规划（Dynamic Programming）
适用场景：
- 用来解决具有最优子结构和重叠子问题的优化问题。
- 问题具有子问题的最优解，可以通过子问题的解来推导出大问题的解。
典型问题：
- 斐波那契数列：通过递推关系来求解第
n项。 - 背包问题：给定物品的重量和价值，选择物品放入背包使得总价值最大，且总重量不超过背包容量。
- 最长公共子序列：求两个字符串的最长公共子序列。
思路：
- 动态规划通过将大问题拆解为小问题，存储每个子问题的解，避免重复计算（通过记忆化或状态转移表）。常常通过一个二维或一维数组来保存结果。
5. 贪心算法（Greedy Algorithm）
适用场景：
- 贪心算法适用于局部最优解可以合并为全局最优解的情况。
- 用于一些求最值（最小/最大）的优化问题。
典型问题：
- 活动选择问题：给定多个活动，选择最多的活动而不冲突。
- 零钱兑换问题：用最少的硬币数兑换某个金额。
- 霍夫曼编码：一种最优编码算法，用来压缩数据。
思路：
- 贪心算法通过在每一步选择当前最优解，逐步逼近全局最优解。适用于某些问题，特别是当问题的局部最优解能带来全局最优解时。
6. 回溯法（Backtracking）
适用场景：
- 用于搜索所有解或满足某些约束的解空间问题，通常通过递归实现。
- 在求解组合问题、排列问题时非常有用。
典型问题：
- N皇后问题：在一个
N x N的棋盘上摆放N个皇后，使得它们互不攻击。 - 全排列/子集问题：给定一个集合，求所有可能的排列或子集。
- 数独求解：通过回溯填充数独格子的每个位置。
思路：
- 回溯法通过递归的方式构造解空间树，逐层深入，如果发现当前路径不可行或不满足条件，就回退到上一个节点进行新的尝试。用于生成所有可能的解或找到符合条件的一个解。
7. 并查集（Union-Find）
适用场景：
- 用于解决动态连通性问题，尤其是在图论中，能够快速判断图中元素是否属于同一个连通分量。
- 适合用于求解连通图、动态连通、网络连接等问题。
典型问题：
- 图的连通分量：判断图中的两个节点是否在同一连通分量中。
- 朋友圈问题：根据一组已知的关系，找出所有的朋友圈。
- 网络连接问题：在一个网络中快速判断两个点是否连通。
思路：
- 并查集通过 路径压缩 和 按秩合并 来优化查找和合并操作。通过 find 和 union 操作来动态维护集合的连通性。
8. 哈希表（Hash Table）
适用场景：
- 用于存储无序的数据并提供高效的查找、插入和删除操作。
- 用于解决查找、去重、计数、频率统计等问题。
典型问题：
- 两数之和：在一个数组中找到和为目标值的两个元素。
- 最长子串：寻找一个字符串中的最长无重复子串。
- 字母异位词：判断两个字符串是否是字母异位词。
思路：
- 哈希表通过哈希函数将数据映射到一个固定的存储位置，从而实现 O(1) 时间复杂度的查找和插入。常用于计数、去重、快速查找等问题。
9. 二分查找（Binary Search）
适用场景：
- 用于在有序数组中查找元素。
- 二分查找可以用于查找目标值、最小/最大值、特定区间等问题。
典型问题：
- 查找元素：在一个有序数组中找到目标元素的位置。
- 求平方根：使用二分查找来计算一个数的平方根。
- 寻找最小的满足条件的值：例如，找出一个数组中第一个大于等于某个值的元素。
思路：
- 二分查找通过每次将搜索范围减半，快速缩小查找空间。常常用于 有序数组 中的查找操作，或者对于某些满足特定条件的区间问题。