📚 XXY的学习笔记

双指针技巧

2026年2月27日
进行中
算法 双指针 数组

概念理解

双指针（Two Pointers）是一种通过使用两个指针协同遍历数据结构的技巧。根据指针的移动方向，可以分为：

  • 相向指针: 两个指针从两端向中间移动
  • 同向指针: 两个指针同向移动，速度可能不同
  • 背向指针: 两个指针从中间向两端移动（较少见）

适用场景

  1. 有序数组中的查找问题
  2. 链表中的环检测、中点查找
  3. 字符串的回文判断、反转
  4. 滑动窗口类问题的基础

可视化演示

相向指针示例

数组: [1, 2, 3, 4, 5, 6, 7]
      ↑                 ↑
     left             right

目标: 找到两数之和等于 8

代码实现

1. 两数之和（有序数组）

def two_sum(nums, target):
    """
    在有序数组中找到两个数，使它们的和等于目标值

    Args:
        nums: 有序数组
        target: 目标和

    Returns:
        两个数的索引，如果不存在则返回 None
    """
    left, right = 0, len(nums) - 1

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

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return None

# 使用示例
nums = [1, 2, 3, 4, 5, 6, 7]
print(two_sum(nums, 8))  # 输出: [0, 6] 或 [1, 5]

2. 反转数组

def reverse_array(arr):
    """
    原地反转数组

    Args:
        arr: 要反转的数组
    """
    left, right = 0, len(arr) - 1

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

    return arr

# 使用示例
arr = [1, 2, 3, 4, 5]
print(reverse_array(arr))  # 输出: [5, 4, 3, 2, 1]

3. 移除元素（同向指针）

def remove_element(nums, val):
    """
    原地移除数组中等于 val 的元素

    Args:
        nums: 数组
        val: 要移除的值

    Returns:
        移除后的数组长度
    """
    slow = 0

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

    return slow

# 使用示例
nums = [3, 2, 2, 3]
val = 3
new_length = remove_element(nums, val)
print(nums[:new_length])  # 输出: [2, 2]

常见问题模板

相向指针模板

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

    while left < right:  # 注意是 < 不是 <=
        # 处理逻辑
        if condition:
            left += 1
        else:
            right -= 1

同向指针模板

def two_pointers_same_direction(arr):
    slow = 0

    for fast in range(len(arr)):
        if condition:
            arr[slow] = arr[fast]
            slow += 1

    return slow

学习心得

  1. 双指针的核心在于减少不必要的遍历
  2. 相向指针适合有序数组，同向指针适合原地修改
  3. 画图理解指针的移动过程非常重要
  4. 注意边界条件：left < right 还是 left <= right

相关题目