双指针（相向）

Source: Dev.to

概览

此模式使用两个指针，分别从数据结构（数组或字符串）的两端开始，向彼此靠拢。它主要在以下情况下使用：

• 两端的顺序都很重要
• 数据已排序或呈对称结构
• 需要检查成对或镜像位置的元素
• 想将时间复杂度从 O(N²) 降低到 O(N)

指针设置

• left → 从索引 0 开始
• right → 从索引 n – 1 开始

循环条件

当 left < right 时继续循环。

指针移动逻辑

• 如果当前条件满足：更新答案并移动指针。
• 如果值太小：将 left 向前移动。
• 如果值太大：将 right 向后移动。

时间 & 空间

• 时间复杂度: O(N)
• 空间复杂度: O(1)

示例

示例 1：Two Sum（已排序数组）

问题:
给定一个已排序的数组，判断是否存在一对元素的和等于目标值。

逻辑:

• 如果和小于目标值，增大 left 以获得更大的和。
• 如果和大于目标值，减小 right 以获得更小的和。

def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return False

示例 2：回文检查

问题:
检查一个字符串是否为回文。

逻辑:

• 对称位置的字符必须相同。
• 任意不匹配立即返回 False。

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

示例 3：盛最多水的容器

问题:
找到两条垂直线，使它们与 x 轴共同构成的容器能够容纳最大的水量。

逻辑:

• 面积取决于宽度和较小的高度。
• 移动较小高度那一侧的指针，以尝试增大面积。

def max_area(height):
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        current_height = min(height[left], height[right])
        max_water = max(max_water, width * current_height)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

示例 4：原地反转数组

问题:
在不使用额外空间的情况下反转数组。

逻辑:

• 交换对称位置的元素。
• 向内移动，直至指针相遇。

def reverse_array(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

    return arr

识别清单

请思考以下问题：

• 是否有两个元素需要相互比较？
• 我们是否关心两端的值？
• 每一步是否可以丢弃一侧的元素？
• 数据是否已排序或呈对称结构？

如果答案是 是，则该模式适用。

总结

• 两个指针从相对两端开始。
• 两者向内部移动。
• 每一次迭代都剔除不可能的情况。

这种方法简洁、最优且易于推理。