常见算法思想与方法

·data-structure-and-algorithm
#algorithm-analysis

常见算法思想与方法

双指针法

双指针法是一种常见且高效的算法思想，适用于有序或需要顺序判断的问题，不适用于无序问题或不允许通过索引访问的问题，需要注意处理边界条件

主要思想是利用两个指针（或称“变量索引”）在数据结构（通常为数组、链表或字符串）上进行遍历

通过同时控制两个指针的位置来缩小问题规模、避免不必要的重复计算，从而达到优化时间复杂度的目的

使用双指针法的原因：

  • 减少重复遍历： 通过两个指针同时处理数据，可以在一次遍历中解决问题，无须使用多重循环，从而降低时间复杂度

  • 空间复杂度较低： 双指针法往往只需要常数级的额外空间，适合内存受限的场景

  • 问题直观： 某些问题自然适合用两个指针来记录不同位置的信息

    • 例如在有序数组中找出和为某个值的两个数时，一个指针从左开始，一个指针从右开始扫描，非常直观高效

使用前需要判断问题是否有顺序性或对称性：

  • 数据是否可以排序？

  • 是否能确定一个“方向”或“窗口”？

个人感觉双指针法本质还是用来遍历数组或字符串的一个常用方法，需要遍历的原因往往是题目出现了某个要遍历之后才能获取到的条件

快慢指针

一个指针移动速度快，另一个移动速度慢，移动方向是相同的

常用于链表结构问题（如判断环形链表、找到链表中间节点）以及数组遍历中某些条件下的选取，或寻找周期性问题

左右指针

一个指针指向起点，另一个指向终点，然后两个指针向中间靠拢

常用于数组排序、两数之和问题、回文字符串判断等问题

同向指针/滑动窗口

两个指针均从头部开始，一个表示窗口的左边界，一个表示窗口的右边界

常用于求数组、字符串中满足一定条件的子区间问题，如最长子串、不超过某个和的子数组等

哈希法

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法

哈希法的核心思想

空间换时间

通过额外开辟一个哈希表（如 map、unordered_map、HashMap 等），将关键数据（键）映射到对应信息（值），从而将原本可能需要 O(n) 扫描查找的操作，降到平均 O(1) 的时间复杂度

快速查找与去重

  • 查找：想知道某个元素或某种状态是否出现过，就把它当作键去哈希表里查找

  • 去重/计数：同一个键只会存一次，或把它映射到一个计数器，从而轻松去重或统计频次

动态更新

遍历（或滑动窗口）过程中，随时把新遇到的元素插入哈希表，并根据需要做查找、删除或修改，灵活应对各种变体

哈希法的一般步骤

无论是“找两数之和”还是“最长无重复子串”“分组异位词”“前缀和计数”……基本都可以归纳为下面几步：

确定“键”（Key）和“值”（Value）

  • 键通常是你需要快速判断、去重或分组的属性

    • 元素本身、前缀和、字符、状态标识等

  • 值一般是你想保留的信息

    • 下标、出现次数、起始位置、其他辅助状态
初始化哈希表

选择合适的数据结构（根据语言，比如 Go 用 make(map[Key]Value)，C++ 用 unordered_map<Key,Value>）

如果需要预估容量，可一次性开大一点以减少扩容开销

遍历或滑动窗口

  • 遍历

    • 对于每个新元素/新状态，先根据题意计算出对应的“查找键”（如 need = target - nums[i]、curSum = 前缀和 等）

    • 在哈希表里查找这个键是否已存在，若存在则根据存的值直接得到答案

    • 若不存在，再把当前元素（或状态）以键–值对的形式插入哈希表

  • 滑动窗口

    • 用左右指针维护子区间，区间变化时同步在哈希表里增删对应的元素，以便快速判断区间内的属性（如是否有重复、各元素频次等）
输出结果或继续推进

一旦在查找阶段命中，就可立刻返回答案

若题目需要全局统计（如所有满足条件的区间数），则继续遍历/滑动直到结束，再汇总结果

KMP 算法

KMP 算法的目前是在长度为 n 的主串（haystack）中高效地查找长度为 m 的模式串（needle），核心思想是利用“已经匹配的前缀”信息，在失配时不回退主串指针，只回退模式串指针，从而跳过不必要的重复比较

这个算法还是太复杂了，并且代码随想录是有讲解视频的，b 站其实应该也有很多讲解，所以暂时这里就先不详细记录了，等后续复习时再回来补充

贪心算法

贪心算法的核心思想是在对问题求解时，每一步都做出在当前看来最优（“贪心”）的选择，希望通过一系列局部最优的决策，最终得到全局最优解

它关注的是每一步的选择，而不是分支或者回溯，整体而言是比较抽象的，也没有一个固定的套路这种的，基本是以经验和直觉为主，只要有局部最优，且想不到反例，合起来就是全局最优，这样就可以试试贪心

动态规划

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解成相互重叠的子问题，并通过“记忆化”避免重复计算，从而高效求解最优解的算法思想

它的核心有两个要素：

最优子结构（Optimal Substructure）

如果一个问题的最优解可以由若干子问题的最优解“合并”而来，且合并方式简单可行，就符合最优子结构

重叠子问题（Overlapping Subproblems）

在分解子问题时，会多次遇到同样的子问题；如果每次都重新计算，就会产生指数级的重复工作

DP 的思路是把每个子问题只算一次，结果存起来，后面再用就直接拿

动态规划的基本步骤

无论是一维、二维、区间、树形还是状态压缩 DP，一般都离不开以下五步：

定义状态

  • 找到“子问题要回答的是什么”

  • 通常用 dp[i]、dp[i][j]、dp[i][j][k] 或者 dp[node]（树形 DP）来表示

确定状态转移方程

写出当前状态如何由更小规模／更低维度的子状态推导：dp[current]=min/max/∑(…dp[sub]…)+cost

初始化（Base Case）

明确最小子问题的答案，比如 dp[0] = 0、dp[1] = 1、空树 dp[nil] = COVERED 等

确定遍历（计算）顺序

  • 对于线性DP，从小到大依次填

  • 区间DP，通常是枚举区间长度再枚举左右端

  • 树形DP，用后序遍历

  • 状态压缩DP，则要枚举状态子集的增量

返回结果

一般是 dp[target] 或者根节点的某个状态