AI summary
type
status
date
slug
summary
category
tags
icon
password
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
对于单链表来说，大部分技巧都属于快慢指针。在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧，本文主要讲数组相关的双指针算法。

快慢指针技巧

原地修改

数组问题中比较常见的快慢指针技巧，是让你原地修改数组。

26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。
高效解决这道题就要用到快慢指针技巧：
我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
相当于是相同的元素只要第一个。

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
其实和数组去重是一模一样的，唯一的区别是把数组赋值操作变成操作指针而已。
除了让你在有序数组/链表中去重，题目还可能让你对数组中的某些元素进行「原地删除」。

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。
和上面一样，只不过这里 nums[0] 也可能等于 val，所以 fast 初始为 0。而且是赋值后再 slow++，所以直接返回 slow 即可。

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
直接调用上面的 removeElement ，然后把后面赋值 0 即可。

滑动窗口

数组中另一大类快慢指针的题目就是「滑动窗口算法」。我在另一篇文章 滑动窗口算法核心代码模板 给出了滑动窗口的代码框架：
具体的题目本文就不重复了，这里只强调滑动窗口算法的快慢指针特性：
left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题。

左右指针的常用算法

二分查找

我在另一篇文章 二分搜索算法核心代码模版 中有详细探讨二分搜索代码的细节问题，这里只写最简单的二分算法，旨在突出它的双指针特性：

n 数之和

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：
我在另一篇文章 一个方法团灭 nSum 问题 中也运用类似的左右指针技巧给出了 nSum 问题的一种通用思路，本质上利用的也是双指针技巧。

反转数组

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
直接左右指针相向而行，然后交换即可。
关于数组翻转的更多进阶问题，可以参见 二维数组的花式遍历技巧。

回文串判断

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。
先实现一个函数 palindrome(s: str, l: int, r: int) -> str ，找到以 s[l] 和 s[r] 为中心的最长回文字符串，然后遍历一遍中心点更新答案即可。