快慢指针
# 快慢指针
快慢指针是方向相同，但是不同步的两个指针。解决这类问题的关键是确定两个指针的移动策略，大多数情况，都需要首先确定循环不变量，定义好循环不变量后，这类问题一般能迎刃而解。我们可大致得出以下模式识别：
- 双指针-快慢指针，首先需要定义循环不变量
在这个章节中，将重点介绍循环不变量的概念。
需要注意的是，循环不变量并不是只针对快慢指针这类题目，只是快慢指针这类题目，尤其需要定义好循环不变量，以免遗漏边界case。
# 图示
这里使用一个动图简要展示快慢指针概念
# 循环不变量
循环不变量是指我们在编写代码中，要一直保持循环不变的性质。循环不变量需要保证变量在初始化、循环中、循环结束三个阶段都保持性质不变。这是我们写对代码的基础，能够避免边界case异常的问题。
双指针中的循环不变量很多时候都指：变量的区间一直符合初始设置。比如设定变量i满足 [0, i)区间，那么就需要在初始化、遍历过程、循环终止，变量i都要在[0, i)这个区间都要满足题目要求。即：
区间不同的定义决定了不同的初始化逻辑、遍历过程中的逻辑。
循环不变量是证明算法有效性的理论依据，也是编码的依据。根据循环不变量就能写对代码。
循环不变量的核心有两点：
- 定义
循环不变量，即对题目要求的那种类型的区间需要定义循环不变量 - 设定其区间，设定好初始区间，然后编码中始终按照该区间编码，使变量在三个阶段都满足该定义
为了更好的展示循环不变量这个概念，这里用双指针中经典的删除元素和荷兰国旗问题两类题目来解释。
# 原地删除元素类问题
这类问题为需要原地删除特定元素，即不需要额外空间，去调整数组符合题目要求。虽然题目会有变化，但是算法的本质都是一样的。
这里用这类问题，核心去阐述在不同定义的循环不变量下编码细节的差异，通过这些差异去感受循环不变量的作用。
# LC 26. 删除有序数组中的重复项 (opens new window)
Q：给你一个 升序排列 的数组 nums ，请你** 原地 (opens new window)** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。不要使用额外的空间，你必须在 原地 (opens new window)修改输入数组 并在使用 O(1) 额外空间的条件下完成。
A：先考虑算法，然后重点根据这道题介绍循环不变量的概念。
# 暴力算法
先忽视不使用额外空间的要求，从暴力解法出发。创建一个不重复数组，然后遍历原数组，当元素与不重复数组的最后一个元素不相等时，说明符合条件，加入到不重复数组的最后。注意，该题的暴力解法，即为这类问题的算法本质。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
// 暴力解法
if (!nums.length) return 0;
// 创建不重复数组
const ans = [nums[0]];
// 当数组元素与 不重复数组 的最后一个元素不相等时，由于数组有序，则说明该元素为不重复元素，可加入到不重复数组
for (let i = 1; i < nums.length; i++) {
if (nums[i] != ans[ans.length - 1]) {
ans.push(nums[i]);
}
}
// 回写到原数组
for (let i = 0; i < ans.length; i++) {
nums[i] = ans[i];
}
return ans.length;
};
# 双指针解法
从暴力解法出发，利用原数组nums fast 指针前面的部门，作为不重复数组，即可节省空间，实现空间复杂度O(1)。
这里重点介绍循环不变量的概念，对于不重复数组的区间有两种设置：[0,slow) 或 [0, slow]，这个区间就被称为循环不变量。循环不变量设定好后，就需要在初始定义、循环体内、结束后 三部分都满足该定义。即对于变量slow的设置，在初始化、循环体内、结束后三部分都满足设定好的区间。
下面对两个区间[0, slow) 和 [0, slow]分别编码，从代码中仔细体会差别。
// 区间 [0, slow)，左闭右开区间
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
// 双指针，快慢指针
// 循环不变量，[0, slow) 表示不重复元素的数组
let slow = 1; // 初始区间 [0, 1)，区间内只有第一个元素，一定是不重复元素数组
let fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[slow - 1]) {
nums[slow] = nums[fast]; // [0, slow)， 因此这里直接对 nums[slow] 赋值
slow++;
}
fast++;
}
// [0, slow) 表示不重复元素的数组，因此返回 slow
return slow;
};
// 区间 [0, slow]，左闭右闭区间
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
// 双指针，快慢指针
// 循环不变量，[0, slow] 表示不重复元素的数组
let slow = 0; // 初始区间 [0, 0]，区间内只有第一个元素，一定是不重复元素数组
let fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
nums[slow + 1] = nums[fast]; // [0, slow]， 因此这里直接对 slow + 1 赋值，即slow后移，扩大不重复数组
slow++;
}
fast++;
}
// [0, slow] 表示不重复元素的数组，因此需要返回slow + 1
return slow + 1;
};
# LC 283. 移动零 (opens new window)
Q：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
A：移动零是一个很经典的题目，利用双指针，定义好非零数组区间。下面给出不同的非零区间定义对应的代码。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
// 双指针
// 循环不变量定义，[0, i)为非零区间Ï
{
// 初始定义 [0, 0)是一个空区间，符合定义
let i = 0;
let j = 0;
while (j < nums.length) {
if (nums[j] != 0) {
// 区间[0,i)，i指向下个元素，因此先赋值后移动
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
}
j++;
}
}
// 循环不变量定义，[0, i] 为非零区间Ï
{
// 初始定义 [0, -1] 是一个空区间，符合定义
let i = -1;
let j = 0;
while (j < nums.length) {
if (nums[j] != 0) {
// 区间[0,i]，i指向非零区间的最后一个元素，因此先移动后赋值
i++;
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
j++;
}
}
};
# LC 27. 移除元素 (opens new window)
Q：给你一个数组 nums 和一个值 val，你需要 原地 (opens new window) 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 (opens new window)修改输入数组。
A：使用双指针，定义好循环不变量，即不包含val的数组区间，下面给出两种区间定义的写法，请体会代码细节的不同。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function (nums, val) {
// 双指针
// 循环不变量定义，不包含val的数组区间为 [0,i)
{
// 初始定义区间为[0, 0)，是一个空间区，是符合区间定义的
let i = 0
let j = 0;
while (j < nums.length) {
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
// 循环不变量定义，不包含val的数组区间为 [0,i]
{
// 初始定义区间为[0, -1]，是一个空间区，是符合区间定义的
let i = -1
let j = 0;
while (j < nums.length) {
if (nums[j] != val) {
i++;
nums[i] = nums[j];
}
j++;
}
return i + 1;
}
};
# LC 80. 删除有序数组中的重复项 II (opens new window)
Q：给你一个有序数组 nums ，请你** 原地 (opens new window)** 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 (opens new window)修改输入数组 并在使用 O(1) 额外空间的条件下完成。
A：使用双指针，定义好循环不变量，即元素最多两次的数组区间。需要注意的是，该题可引申为最多k个重复元素，解法是一样的。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
// 双指针
{
// 循环不变量，最多重复两次数组区间 [0, i)
// 初始定义区间 [0, 3)，区间内有两个元素，是符合定义的
let i = 2;
let j = i;
while (j < nums.length) {
if (nums[j] != nums[i - 2]) {
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
{
// 循环不变量，元素最多重复两次数组区间 [0, i]
// 初始定义区间，[0,1]，区间内有两个元素，是符合定义的。注意 j 的定义，
let i = 1;
let j = i + 1;
while (j < nums.length) {
if (nums[j] != nums[i - 1]) {
i++;
nums[i] = nums[j];
}
j++;
}
return i + 1;
}
};
# 荷兰国旗问题
荷兰国旗问题是双指针中一个经典的题目，请从本题中体会不同的循环不变量定义，对编码细节的差异。
# LC 75. 颜色分类 (opens new window)
Q：给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
A：算法核心思路是利用快排的分治思想，利用双指针对数字进行排序，这里我们直接上代码，给出两种不同的循环不变量定义对应的代码，请仔细体会。如果对算法本身有疑惑，可参考力扣该题对应的题解。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
// 双指针
const swap = (x, y) => {
let tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
// 循环不变量，0: [0, p0)，1: [p0, i)，2: (p2, n-1]
{
// 初始区间定义 0: [0, 0)，1: [0, 0)，2: (n-1, n-1] 都 为空区间，是符合定义的
const n = nums.length;
let p0 = 0;
let p2 = n - 1;
let i = 0;
// 考虑区间 1: [p0, i)，2: (p2, n-1]，对于两个区间 i 都是开区间，因此需要判断 i == p2 的情况
while (i <= p2) {
if (nums[i] == 0) {
// 红
swap(p0, i);
p0++;
i++;
} else if (nums[i] == 1) {
i++;
} else {
// nums[i] == 2，注意元素交换后，i位置的元素还没遍历过，因此这里不一定i指针
swap(i, p2);
p2--;
}
}
}
// 循环不变量，0: [0, p0]，1: (p0, i)，2: [p2, n-1]
{
// 初始区间定义，0: [0, -1]，1: (-1, 0)，2: [n, n-1]，三个区间都为空区间，是符合区间定义的
const n = nums.length;
let p0 = -1;
let i = 0;
let p2 = n;
// 因为 1: (p0, i)，2: [p2, n-1]，两个区间，一个为右开一个为左闭，因此当 i == p2时，该元素已经确定为2，遍历结束
while (i < p2) {
if (nums[i] == 0) {
p0++;
swap(i, p0);
i++;
} else if (nums[i] == 1) {
i++;
} else {
// nums[i] == 2
p2--;
swap(i, p2);
}
}
}
};
# 其他
# LC 674. 最长连续递增序列 (opens new window)
Q：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
A：使用双指针，当右指针符合递增条件时，序列长度+1，不符合时，移动左指针。
本题的循环不变量为严格递增序列，对区间有两种定义方式：[left, right] 和 [left ,right) ，下面给出两种区间定义的写法，注意仔细体会细节的不同。算法是一致的，核心就是不同的区间定义，会导致编码细节的不同
/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function (nums) {
// 双指针
// 循环不变量，严格单调递增区间：[left, right)
{
// 初始定义区间 [0, 0), 初始区间为空区间，是符合单调递增定义的
let left = 0;
let right = 0;
let max = 0;
while (right < nums.length) {
if (right > 0 && nums[right] <= nums[right - 1]) {
left = right;
}
// 因为单调递增区间为：[left, right)，所以需要先看到right，所以right++在前
right++;
// 对于区间 [left, right) 长度为：right - left
max = Math.max(max, right - left);
}
return max;
}
// 循环不变量，严格单调递增区间 [left, right]
{
// 初始区间 [0, 0]，只有一个元素，是符合单调递增定义的
let left = 0;
let right = 0;
let max = 0;
while (right < nums.length) {
if (right > 0 && nums[right] <= nums[right - 1]) {
left = right;
}
// 单调递增区间为 [left, right]，因此区间长度为 right - left + 1，且应该先计算区间长度
max = Math.max(max, right - left + 1);
// 然后再移动右指针
right++;
}
return max;
}
};
最后，需要注意的是，尽量避免使用全程用直觉写代码。直觉能帮我们思考出初始算法，然后需要定义好循环不变量，严格按照循环不变量来编码。下面给出一个错误的答案，下面的答案会遗漏边界case
// 该解法，会对 [2], [2,2,2,2]等边界case 给出错误答案
// 修复的方法也很简单，初始使 max = 1即可，但是这种做法没有定义循环不变量，当问题复杂以后，边界case较多的情况下，很容易出错
var findLengthOfLCIS = function (nums) {
// 双指针
let left = 0;
let right = 1;
let max = 0;
while (right < nums.length) {
if (nums[right] > nums[right - 1]) {
max = Math.max(max, right - left + 1);
} else {ƒ
left = right;
}
right++;
}
return max;
};
# LC 485.最大连续-1-的个数 (opens new window)
Q：给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
A：双指针，快慢指针，核心定义好循环不变量。（这是一道简单题，简单可使用count计数，这里只介绍循环不变量）
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function (nums) {
//双指针，快慢指针
// 循环不变量：连续为1的区间 [left,right)
{
// 初始定义为 [0, 0) 空区间，符合区间定义
let left = 0;
let right = 0;
let maxL = 0;
while (right < nums.length) {
// 区间定义 [left,right)，因此看到nums[right]后就需要让 right++ 移动一位
if (nums[right++] != 1) {
left = right;
}
// 区间定义 [left,right)，区间长度为 right - left
maxL = Math.max(maxL, right - left);
}
return maxL;
}
// 注意，对于本题 [left, right]区间比较难设计，因为 [0,0]初始区间有一个元素，但是该元素不为空，且不知道该元素的具体值
};