算法入门很简单：算法题的破解之道上篇
模式一：滑动窗口
滑动窗口用于对给定数组和链表的特定窗口大小执行所需的操作
问题输入是线性数据结构。例如链表、数组或字符串
要求找到最长/最短的子字符串，子数组或所需的值
题目练习
1. 大小为 K 的最大总和子数组（简单）
2. 给定总和的最小子数组（简单）
3. 最长的具有 K 个不同字符的子字符串（中）
模式二：双指针
“两个指针”是一种模式，其中两个指针串联遍历数据结构，直到一个或两个指针都达到特定条件。两个指针在排序数组或链接列表中搜索对时通常很有用；例如，当您必须将数组的每个元素与其他元素进行比较时。
需要两个指针，因为只有一个指针，您将不得不不断地循环遍历数组以找到答案。用单个迭代器来回进行此操作对于时间和空间复杂度而言效率低下-一种称为渐近分析的概念。尽管使用 1 个指针的强力或幼稚的解决方案将起作用，但它将产生类似于 O（n²）的东西。在许多情况下，两个指针可以帮助您找到具有更好空间或运行时复杂性的解决方案。
确定何时使用“两指针”方法的方法：
在处理排序数组（或链接列表）并且需要找到一组满足某些约束的元素时，它将遇到一些问题。
数组中的元素集是一对，三元组甚至是子数组以下是具有两个指针模式的一些问题：
平方排序数组（简单）
总计为零的三元组（中）
比较包含退格键的字符串（中）
模式三：快慢指针
快速和慢速指针方法，也称为 Hare＆Tortoise 算法，是一种指针算法，它使用两个指针以不同的速度在数组（或序列/链接列表）中移动。 处理循环链表或数组时，此方法非常有用。
通过以不同的速度移动（例如，在循环链表中），该算法证明两个指针必然会合。一旦两个指针都处于循环循环中，快速指针应捕获慢速指针。
您如何确定何时使用快速和慢速模式？
该问题将处理链表或数组中的循环
当您需要知道某个元素的位置或链表的总长度时。什么时候应该在上面提到的“两指针”方法上使用它？
在某些情况下，您不应该使用“两指针”方法，例如在单链列表中，您不能向后移动。何时使用快速和慢速模式的一个示例是当您试图确定链接列表是否为回文式时。具有快速和慢速指针模式的问题：
链接列表周期（简单）
回文链接列表（中）
循环循环阵列（硬）
模式四：合并间隔
合并间隔模式是处理重叠间隔的有效技术。在很多涉及间隔的问题中，您需要找到重叠的间隔，或者如果它们重叠，则需要合并间隔。该模式如下所示：
给定两个间隔（“ a”和“ b”），两个间隔可以通过六种不同的方式相互关联：
了解和认识这六个情况将帮助您解决从插入间隔到优化间隔合并的各种问题。
您如何确定何时使用“合并间隔”模式？
如果要求您仅以互斥间隔生成列表
如果您听到术语“重叠间隔”。
合并间隔问题模式：
区间相交（中）
最大 CPU 负载（硬）
模式五：循环排序
此模式描述了一种有趣的方法来处理涉及包含给定范围内的数字的数组的问题。循环排序模式一次在数组上迭代一个数字，如果要迭代的当前数字不在正确的索引处，则将其与在其正确的索引处的数字交换。您可以尝试将数字放置在正确的索引中，但这会导致 O（n ^ 2）的复杂度不是最优的，因此是循环排序模式。
如何识别这种模式？
它们将是涉及编号在给定范围内的排序数组的问题
如果问题要求您在排序/旋转数组中查找缺失/重复/最小的数字具有循环排序模式的问题：
查找丢失的号码（简单）
查找最小的遗漏正数（中）
模式六：就地反转链表
在很多问题中，可能会要求您反向链接列表的一组节点之间的链接。通常，约束是您需要就地执行此操作，即使用现有的节点对象而不使用额外的内存。这是上面提到的模式有用的地方。
此模式一次反转一个节点，其中一个变量（当前）指向链接列表的开头，而一个变量（上一个）将指向您已处理的上一个节点。以锁定步骤的方式，您可以通过将当前节点指向上一个节点来反转该节点，然后再移动到下一个节点。另外，您将更新变量“ previous”以始终指向您已处理的上一个节点。
如何确定何时使用此模式：
如果要求您在不使用额外内存的情况下反向链接列表链表模式就地反转的问题：
撤消子列表（中）
反转每个 K 元素子列表（中）
宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入
🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖，江湖却没有我的影子 热爱技术，专注于后端全栈，轻易不换岗 拒绝内卷，工作于软件工程师，弹性不加班 热衷分享，执着于阅读写作，佛系不水文
评论