在上一篇文章 算法模式：区间合并 介绍了合并区间所用的算法模式。本篇文章，介绍一个即可以用在数组，又可以用在链表中的算法模式：双指针。
双指针 双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。
需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效，但时间复杂度一般会是 \$O(n^2)\$。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。
识别使用双指针的招数：
一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件
这种组合可能是一对数，三个数，或是一个子数组
LeetCode 15. 三数之和 LeetCode - 15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
在上一篇文章 算法模式：双指针 介绍了双指针模式。本篇文章，再介绍一个即可以用在数组，又可以用在链表中的算法模式：快慢指针。快慢指针，其实是双指针模式的一个变种。所以，两者在很多地方有相通之处。
快慢指针 快慢指针模式，有一个非常出名的名字，叫龟兔赛跑。大家肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针：这种算法的两个指针的在数组上（或是链表上，序列上）的移动速度不一样。还别说，这种方法在解决有环的链表和数组时特别有用。
通过控制指针不同的移动速度（比如在环形链表上），这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个（可以想象成跑道上面跑得快的人套圈跑得慢的人）。
咋知道需要用快慢指针模式勒？
问题需要处理环上的问题，比如环形链表和环形数组
当你需要知道链表的长度或是某个特别位置的信息的时候
那啥时候用快慢指针而不是上面的双指针呢？
有些情形下，咱们不应该用双指针，比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。
LeetCode 141. 环形链表 LeetCode - 141. 环形链表 给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
在上一篇文章 算法模式：改进的二分查找 介绍了二分查找以及相关变种。本篇文章，继续介绍数组相关的算法模式：区间合并。
区间合并 区间合并模式是一个用来处理有区间重叠的很高效的技术。在涉及到区间的很多问题中，通常咱们需要要么判断是否有重叠，要么合并区间，如果他们重叠的话。这个模式是这么起作用的。
给两个区间，一个是 a，另外一个是 b。别小看就两个区间，他们之间的关系能跑出来6种情况。详细的就看图啦。
图 1. 区间关系 观察这六种排序，明显后三种排序是前三种排序的一个“变种”：对区间根据起点和终点进行排序，就是剩下前三种排序了。再对其进行合并就很简单了：
没有重叠，则直接开启新区间。
有重叠，起点和终点分别取最大值和最小值即可：由于区间已经排序，则相邻两个区间的起点是前面区间的起点，重点则是两个区间终点的最大值。
LeetCode 56. 合并区间 LeetCode - 56. 合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti<= endi<= 104
思路分析 上面已经分析过解题思路，这里直接上代码：
在上一篇文章 算法模式：前缀和 介绍了前缀和的算法模式。本篇文章，继续介绍数组相关的算法模式：改进的二分查找。
二分查找 二分查找相比每一个学过计算机算法的小伙伴都了解，时间复杂度是： \$\log_2N\$，是一个非常高效的数组查找算法。当然，前提是数组必须有序。过程如下：
图 1. 二分查找 LeetCode 704. 二分查找 就是一个标准的二分查找的算法题。代码如下：
/** * @author D瓜哥 · https://www.diguage.com * @since 2024-09-14 19:52:26 */ public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } 除了在排序数组中查找特定的值，二分查找还可以用于找边界和在旋转数组中查值。
找边界：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 \$log_2n\$ 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
在上一篇文章 算法模式：差分数组，本篇文章，继续介绍数组相关的算法模式：前缀和。
前缀和 前缀和可以简单理解为「数列的前 n 项的和」。具体过程如图所示：
图 1. 前缀和 这是一种重要的预处理方式，也就是需要额外的空间并且提前计算好这些值。如果使用得当，能大大降低查询的时间复杂度。
LeetCode 303. 区域和检索 - 数组不可变 LeetCode - 303. 区域和检索 - 数组不可变 给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的 总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )
Christopher Alexander 在 《建筑的永恒之道》 中说：“每一个模式描述了一个在我们周围不断重复发生的问题，以及该问题的解决方案的核心。这样，你就能一次又一次地使用该方案而不必做重复劳动。”受此影响，GoF 总结经验，写出了著名的 《设计模式》。
在算法中，也有很多类似设计模式这样的解决方案。D瓜哥称其为“算法模式”。后面，慢慢写文章一一介绍一下。由浅及深，今天先来介绍最简单的一个模式：差分数组。
差分数组 差分数组：差分数组就是原始数组相邻元素之间的差。举例如下：
下标 0 1 2 3 4 5 原始数组
5
9
2
6
5
3
差分数组
5
4
-7
4
-1
-2
差分数组是从原始数组构造出来的一个辅助数组，表示相邻元素直接的差值。可用于解决需要对数组一个区间内同时做加减的操作。比如：随着公交站各个站台上下车，判断公交车是否超载。
LeetCode 370. 区间加法 LeetCode - 370. 区间加法 假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。