双指针（同向）

Source: Dev.to

请提供您希望翻译的完整文本内容（除代码块和 URL 之外），我将按照要求将其翻译成简体中文并保持原有的格式。

概述

双指针（同向）模式使用两个索引一起向前移动遍历数据结构（通常是数组或字符串）。
与相反方向的指针不同，两个指针仅从左 → 右移动，但速度不同或基于条件。
该模式在线性时间优化中极为常见。

When to Use Two Pointers (Same Direction)

使用此模式的情形：

• 按 顺序 处理元素。
• 需要 比较或关联两个位置。
• 需要 跳过、过滤或跟踪一个范围。
• 想避免嵌套循环（O(N²））。

Typical Problem Statements

• 删除已排序数组中的重复项
• 检查一个数组是否是另一个数组的子序列
• 最长不含重复字符的子串
• 合并两个已排序数组
• 根据条件对数组进行划分
• 快慢指针问题（变体）

核心直觉

• 读取器 & 写入器
• 慢速 & 快速
• 锚点 & 探索者

一个指针表示参考位置，另一个向前扫描。

通用算法模板

slow = 0
for fast in range(0, n):
    if condition_satisfied:
        # perform operation using slow & fast
        slow += 1

• fast 在 每次迭代 中移动。
• slow 仅在 需要时 移动。

关键属性

• Time Complexity: O(N)
• Space Complexity: O(1)
• 最适用于 sorted arrays or strings。
• 避免不必要的比较。

示例 1 – 从已排序数组中移除重复项

问题
给定一个已排序的数组，原地移除重复项并返回新的长度。

思路
fast 扫描元素，slow 标记写入唯一值的位置。

代码

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

示例 2 – 检查子序列

问题
检查字符串 s 是否是字符串 t 的子序列。

思路
slow 跟踪在 s 中的位置，fast 扫描 t。

代码

def is_subsequence(s, t):
    slow = 0
    for fast in range(len(t)):
        if slow < len(s) and s[slow] == t[fast]:
            slow += 1
    return slow == len(s)

示例 3 – 最长不含重复字符的子串

问题
找出不含重复字符的最长子串的长度。

思路
left 和 right 都向前移动；使用集合来维护唯一性。

代码

def longest_unique_substring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

示例 4 – 合并两个已排序数组

问题
将两个已排序的数组合并为一个已排序的数组。

思路
指针 i 用于第一个数组，指针 j 用于第二个数组；两者向前移动。

代码

def merge_sorted(a, b):
    i = j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])
    return result

与滑动窗口的区别

常见错误

• 盲目移动两个指针。
• 忘记指针的边界。
• 在顺序重要时将其用于未排序的数据。
• 将其与相反方向的指针混淆。

如何识别此模式

自问：

• 我是否只需要向前扫描一次？
• 是否可以让一个指针跟踪进度，而另一个指针向前扫描？
• 顺序是否重要？

如果你可以用这种扫描来替代嵌套循环，则适用该模式。

心理模型

想象：

• 一个指针向前走。
• 另一个指针记录一个引用。
• 两者都向前移动，从不后退。

概述

最终思考

这种模式弥合了暴力破解和最优解之间的差距。
一旦掌握，你会本能地用简洁的线性扫描来替代嵌套循环。