快慢指针-从leetcode题目说起
我是天空里的一片云，偶尔投影在你的波心。 --偶然
前言
先来看一道算法题：27.移出元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例
例如：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] ，给定nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3]
想必各位第一时间想到的是JavaScript的splice函数，使用 for 循环，依次遍历数组，找到等于 val 的元素并删除，
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
const removeElement = function (nums, val) {
let len = nums.length;
for (let i = 0; i < len; i++) {
if (nums[i] === val) {
nums.splice(i, 1);
len--;
i--;
}
}
return len;
};
这样看，这道题这道题很简单是不是？直接使用了 JavaScript 的 API，简单直接
好了，现在恭喜你，喜提一个称号，API 调用工程师，请戴好帽子🎩(可个玩笑
那么我们再看看这样的执行速度呢？
Oops，好像并不理想，内存占用只高于27.04%，
实际上，我们这样做，就失去了这道题的意义，这道题考察的是对于数组的理解：
从数组说起
我们都知道，数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数组是一片连续的内存空间(这里只讨论狭义的数组，快数组慢数组不在讨论范围),而且数组没有删除操作，如果想要删除一个元素，在数组内部是比较复杂的操作，需要将即将删除的下表的位置依次覆盖，
比如，数组 a,b,c 对应的下标依次是 1、2、3，如果我们要删除元素a，那么就需要将 a 后面的元素依次前移，由 a、b、c，对应下表 1、2、3，变为 b、c，对应下表 1、2、3，
了解了数组的删除操作，那么在这里，我们是不是可以复原一下这个思路呢？
暴力算法
知道了解题思路，我们是不是就可以开始着手解决问题了。
首先想到的是双层 for 循环的暴力解法，第一层 for 是找出需要删除的元素，第二层 for 是依次将后面的元素向前移动，覆盖需要删除的位置。
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
/**
*
* @param nums
* @param val
* @returns {*}
*/
function removeElementFor(nums, val) {
let size = nums.length;
for (let i = 0; i < size; i++) {
if (nums[i] === val) { // 发现需要移除的元素，就将数组集体向前移动一位
for (let j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
这种算法并不需要太深入的思考
双指针
那么我们可否优化一下暴力解法，记录下当前需要删除的位置？
实际上，我们可以用两个指针，分别为快慢指针，快指针用于遍历所有元素，慢指针用于记录下当前除去需要删除的元素的下标，
这里借用卡尔老师代码随想录的图：代码随想录，卡尔老师的算法讲解的不错，大家可以去瞅瞅
上代码：
/**
* @param {number[]} nums
* @param val
* @returns {number}
*/
const removeElement1 = (nums, val) => {
let slow=0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== val) {
nums[slow++] = nums[i];
}
}
return slow;
}
看一下执行结果：
可以看到，使用快慢指针后，代码执行时间以及代码执行的内存都有了巨大的提升。
总结
在了解数组删除原理的基础上，我们可以使用双指针的思路来解决。顺便说一下，对于算法题，我们尽量不要使用库函数，因为算法题本身就是对于我们思维的一个学习历练过程，直接使用库函数，一行代码把原来需要解决的问题给搞定了，也就失去了是考的过程了。
链接
更多快慢指针题目