在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
对于单链表来说，大部分技巧都属于快慢指针，前文链表篇 都涵盖了，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧，本文主要讲数组相关的双指针算法
数组问题中比较常见的快慢指针技巧，是让你原地修改数组。
比如说看下力扣第 26 题「删除有序数组中的重复项」，让你在有序数组去重：
Tip
简单解释一下什么是原地修改：
如果不是原地修改的话，我们直接 new 一个int[]数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。
但是现在题目让你原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。
由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。
高效解决这道题就要用到快慢指针技巧：
Done
我们让慢指针
slow走在后面，快指针fast走在前面探路，找到一个不重复的元素就赋值给slow并让slow前进一步。
这样，就保证了nums[0..slow]都是无重复的元素，当fast指针遍历完整个数组nums后，nums[0..slow]就是整个数组去重之后的结果。
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
代码可视化：
双指针技巧秒杀七道数组题目 | labuladong 的算法笔记
算法执行的过程如下 GIF 图：
这个可能更清楚些
再简单扩展一下，看看力扣第 83 题「删除排序链表中的重复元素」，如果给你一个有序的单链表，如何去重呢？
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
算法执行的过程请看下面这个 GIF：
Question
这里可能有读者会问，链表中那些重复的元素并没有被删掉，就让这些节点在链表上挂着，合适吗？
这就要探讨不同语言的特性了，像 Java/Python 这类带有垃圾回收的语言，可以帮我们自动找到并回收这些「悬空」的链表节点的内存，而像 C++ 这类语言没有自动垃圾回收的机制，确实需要我们编写代码时手动释放掉这些节点的内存。
不过话说回来，就算法思维的培养来说，我们只需要知道这种快慢指针技巧即可。
除了让你在有序数组/链表中去重，题目还可能让你对数组中的某些元素进行「原地删除」。
比如力扣第 27 题「移除元素」，看下题目：
题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
这和前面说到的数组去重问题解法思路是完全一样的
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
注意这里和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。
实现了这个 removeElement 函数，接下来看看力扣第 283 题「移动零」：
给你输入一个数组 nums，请你原地修改，将数组中的所有值为 0 的元素移到数组末尾
比如说给你输入 nums = [0,1,4,0,2]，你的算法没有返回值，但是会把 nums 数组原地修改成 [1,4,2,0,0]。
结合之前说到的几个题目，你是否有已经有了答案呢？
题目让我们将所有 0 移到最后，其实就相当于移除 nums 中的所有 0，然后再把后面的元素都赋值为 0 即可。
所以我们可以复用上一题的 removeElement 函数：
void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
int p = removeElement(nums, 0);
// 将 nums[p..] 的元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 见上文代码实现
int removeElement(int[] nums, int val);
到这里，原地修改数组的这些题目就已经差不多了。数组中另一大类快慢指针的题目就是「滑动窗口算法」。
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
/* 滑动窗口算法框架 */
public void slidingWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) valid++;
}
while (window needs shrink) {
char d = s.charAt(left);
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid--;
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
}
具体的题目本文就不重复了，这里只强调滑动窗口算法的快慢指针特性：
left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题.