双指针算法：七道 LeetCode 经典题解

双指针是一种比较常见的算法思路。通过两个指针在数组、字符串或链表中移动，可以减少不必要的遍历，也能在某些情况下实现原地修改。

不过，双指针并不是只有一种固定的写法。根据题目要求，两个指针的移动方式也有所不同。

这篇文章主要记录三种用法：

• 快慢指针：两个指针通常从同一侧出发，一个负责遍历，一个负责维护已经处理好的部分。
• 左右指针：分别从数组或字符串的两端出发，逐渐向中间靠拢。
• 中心扩散：以某个位置为中心，让两个指针分别向左右扩展。

下面结合七道 LeetCode 题目，分别看看这些思路如何应用。

一、快慢指针

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

这道题要求删除有序数组中的重复元素，使每个元素只出现一次，并返回去重后的元素数量。

如果允许额外使用一个数组，最容易想到的方法就是遍历原数组，将不重复的元素依次存入新数组。

不过，题目要求原地修改数组，因此这里采用快慢指针。

两个指针分别负责不同的工作：

• fast：向后遍历，寻找新的、不重复的元素。
• slow：指向当前有效区间的最后一个元素。

由于数组已经排好序，相同的元素会排列在一起，所以只需要比较 nums[fast] 和 nums[slow]。

如果两者相同，说明遇到了重复元素，让 fast 继续向后移动即可。

如果两者不同，就说明找到了一个新元素。此时先将 slow 加一，再把新元素写入 nums[slow]。

例如：

原数组：[1, 1, 2]
索引：    0  1  2

初始时，slow 和 fast 都指向索引 0。

当 fast 移动到第二个 1 时，由于它与 nums[slow] 相同，直接跳过。

继续移动到 2，发现它与 nums[slow] 不同，于是先让 slow 移动到索引 1，再将 2 写入该位置。

此时数组的有效部分就变成了：

[1, 2, ...]

这里的 slow 始终指向有效区间的最后一个位置，因此处理完成后，有效区间为 [0, slow]，长度就是 slow + 1。

Python 代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
        return slow + 1

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

这道题的思路与第 26 题基本相同，只不过操作对象从数组变成了链表。

同样使用快慢指针：

• fast 负责遍历链表，寻找不同的节点。
• slow 指向当前保留下来的最后一个节点。

当 fast.val 与 slow.val 相同时，说明这个节点的值已经出现过，直接让 fast 继续向后移动。

如果两者不同，就通过：

slow.next = fast
slow = slow.next

将找到的新节点连接到有效链表的末尾，同时更新 slow 的位置。

这里和数组去重最大的区别在于：数组通过覆盖元素实现原地修改，而链表通过修改 next 指针跳过重复节点。

还有一个容易忽略的细节。

当遍历结束时，slow 后面可能仍然连接着原链表中尚未断开的重复节点。

因此，如果 slow 不为空，还需要执行：

slow.next = None

将有效链表的末尾断开，避免结果中残留重复元素。

Python 代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast != None:
            if fast.val != slow.val:
                slow.next = fast
                slow = slow.next
            fast = fast.next
        if slow != None:
            slow.next = None
        return head

3. LeetCode 27. 移除元素

这道题要求在原数组中移除所有等于 val 的元素，并返回剩余元素的数量。

思路仍然是快慢指针，不过这里的 slow 与第 26 题有所不同。

• fast：负责遍历原数组。
• slow：指向下一个应该写入有效元素的位置。

每当 fast 找到一个不等于 val 的元素，就把它写入 nums[slow]，然后让 slow 加一。

如果当前元素等于 val，则直接跳过。

例如：

nums = [3, 2, 2, 3]
val = 3

初始时两个指针都位于索引 0。

第一个元素是 3，需要移除，因此只移动 fast。

当 fast 到达索引 1，遇到元素 2 时，就将它写入 nums[slow]，也就是覆盖索引 0 上的 3。

继续遍历，第二个 2 也会被保留下来。

最终数组的有效部分为：

[2, 2, ...]

此时 slow = 2，表示已经保留了两个元素，因此直接返回 slow。

Python 代码：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

这里可以和第 26 题对比一下：

• 第 26 题中，slow 指向最后一个有效元素，所以返回 slow + 1。
• 第 27 题中，slow 指向下一个写入位置，同时也表示已经保留的元素数量，所以直接返回 slow。

虽然两道题都使用快慢指针，但指针的定义不同，返回值自然也不一样。

4. LeetCode 283. 移动零

这道题要求将数组中的所有 0 移动到末尾，同时保持非零元素之间的相对顺序，并且不能额外创建一个数组。

其实可以直接沿用第 27 题的思路。

首先使用快慢指针，将所有非零元素依次写到数组前面：

• fast 遍历整个数组。
• slow 指向下一个非零元素应该写入的位置。
• 遇到非零元素时，将其写入 nums[slow]，然后移动 slow。
• 遇到 0 时，直接跳过。

完成这一步后，数组前面已经保存了所有非零元素。

不过，第 27 题只要求返回有效长度，而这道题要求将整个数组修改成正确结果。

因此，还需要将索引 slow 到数组末尾的所有位置填成 0。

例如：

原数组：[0, 1, 0, 3, 12]

非零元素前移后：
[1, 3, 12, 3, 12]

将剩余位置填零：
[1, 3, 12, 0, 0]

这样既能把所有零移动到末尾，也能保留非零元素原来的相对顺序。

Python 代码：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        for i in range(slow, len(nums)):
            nums[i] = 0

可以发现，第 27 题与第 283 题在移动有效元素时，使用的几乎是同一套逻辑。

区别只是：前者只关心保留多少个元素，而后者还要将剩余的位置全部填零。

二、左右指针

前面几道题都是让两个指针从同一侧出发。接下来换一种方式，让两个指针分别从数组或字符串的两端向中间移动。

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

这道题要求在一个已经按非递减顺序排列的数组中，找出两个元素，使它们的和等于 target。

最直接的方法是使用双重循环，枚举所有数对，逐个检查两数之和是否等于目标值。

不过，这种方法的时间复杂度为 $O(n^2)$。

既然题目已经告诉我们数组是有序的，就可以利用这个条件，采用左右指针来减少枚举次数。

首先定义两个指针：

• left：从数组第一个元素开始。
• right：从数组最后一个元素开始。

每次计算两个指针指向的元素之和：

s = nums[left] + nums[right]

然后根据结果决定移动哪个指针。

如果 s < target：

说明当前两数之和太小，需要尝试更大的数。

由于数组已经有序，可以将 left 向右移动。

如果 s > target：

说明当前两数之和太大，需要尝试更小的数，因此将 right 向左移动。

如果 s == target：

说明找到了符合条件的两个元素，直接返回对应位置。

整个过程中，只需要让 left < right，就能保证不会使用同一个位置的元素两次。

Python 代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums) - 1
        while left < right:
            s = nums[left] + nums[right]
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                return [left + 1, right + 1]

这里还需要注意题目对返回位置的要求。

Python 的数组下标从 0 开始，但本题要求返回的位置从 1 开始，因此找到答案后，需要将两个索引分别加一。

由于每次循环至少有一个指针向中间移动，两个指针最多移动 O(n) 次，所以整体时间复杂度为 $O(n)$。

6. LeetCode 344. 反转字符串

这道题要求原地反转一个字符数组。

同样可以使用左右指针，让它们分别指向数组的首尾。

每次交换两个指针指向的字符，然后同时向中间移动：

s[left], s[right] = s[right], s[left]

例如：

原数组：['h', 'e', 'l', 'l', 'o']

交换首尾：
['o', 'e', 'l', 'l', 'h']

交换第二个和倒数第二个：
['o', 'l', 'l', 'e', 'h']

当两个指针相遇或交错时，就说明需要交换的位置都已经处理完毕。

Python 代码：

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

这道题的实现比较简单，主要就是利用左右指针完成原地交换，不需要额外创建一个反转后的数组。

三、中心扩散

7. LeetCode 5. 最长回文子串

这道题要求找出字符串中最长的回文子串。

所谓回文串，就是从左往右和从右往左读取，得到的字符顺序相同。例如：

abcba

对于回文串，可以观察到一个特点：它的左右两侧是对称的。

因此，我们可以枚举回文串的中心，再从中心向左右两侧不断扩散，寻找以该位置为中心的最长回文子串。

不过，回文串的长度有两种情况。

奇数长度的回文串

例如：

a b c b a
    ↑
    中心

这种情况下，中心就是某一个字符，因此可以让 left 和 right 从同一个位置开始：

left = right = i

偶数长度的回文串

例如：

a b b a
  ↑ ↑
  中心

偶数长度的回文串没有单独的中心字符，而是以两个相邻字符之间的位置为中心。

因此，可以让两个指针分别从 i 和 i + 1 开始。

7.1 编写中心扩散函数

为了避免重复编写扩散逻辑，可以先将它封装成一个函数。

    def func(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1 : right]

这里的 while 循环会不断检查左右字符是否相同。

如果相同，就说明当前范围仍然满足回文条件，可以继续向外扩散。

如果两个字符不相同，或者其中一个指针已经越过字符串边界，就停止扩散。

需要注意的是，循环退出时，左右指针已经位于有效回文范围之外。

因此，返回子串时应该使用：

s[left + 1 : right]

其中，left + 1 是有效回文串的起始位置，而 Python 切片的右端点不包含在结果中，所以可以直接使用 right。

7.2 枚举所有可能的中心

有了中心扩散函数后，接下来就可以遍历字符串中的每个位置。

对于位置 i，分别检查：

• 以 i 为中心的奇数长度回文串。
• 以 i 和 i + 1 为中心的偶数长度回文串。

将两种情况下得到的回文串与当前最长结果比较，如果找到了更长的，就更新答案。

Python 完整代码：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            s1 = self.func(s, i, i)
            s2 = self.func(s, i, i + 1)
            res = res if len(res) > len(s1) else s1
            res = res if len(res) > len(s2) else s2
        return res

    def func(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1 : right]

这里有一个细节：func() 会先检查左右指针是否越界，再比较对应位置的字符。

因此，当扩散到字符串边界时，循环会自动停止，不会发生下标越界的问题。

对于长度为 n 的字符串，需要枚举 O(n) 个中心，每个中心最坏可能向两侧扩散 O(n) 次，因此整体时间复杂度为 $O(n^2)$。

虽然这里也使用了两个指针，但它与前面的快慢指针、左右指针有所不同：中心扩散需要对不同的中心重新开始搜索，不能直接利用两个指针单向移动的特点将时间复杂度降到 O(n)。

四、总结

这七道题虽然都使用了双指针，但指针的作用和移动方式并不完全相同。

其中，前四道题的思路最为接近，尤其是第 26、27、283 题，都可以通过快慢指针维护数组前面的有效部分。

不过，写代码时一定要先明确 slow 的含义：它究竟指向最后一个有效元素，还是下一个可以写入的位置？两种定义都会影响赋值顺序和最终返回值。

对于左右指针，重点则是判断什么时候移动左指针、什么时候移动右指针，以及为什么这样移动不会漏掉答案。

中心扩散又有所不同，需要分别考虑奇数和偶数长度的回文串。

我觉得双指针最值得掌握的并不是某一份固定模板，而是根据题目要求，明确两个指针各自负责什么，再确定它们的移动规则。