双指针

本章目标：掌握对撞指针、快慢指针、归并指针三大模板，能秒杀所有 Easy 级双指针题。

你将学到

• 对撞指针（两端向中间）
• 快慢指针（同向不同速）
• 归并指针（两个序列同步）
• 原地删除/移除元素
• 判断回文

1. 概念

双指针是最基础也最高频的算法技巧，核心思想是用两个指针协同遍历，减少嵌套循环。根据指针运动方式分为三类：

• 对撞指针：left 从左、right 从右，向中间逼近。适合有序数组上的问题。
• 快慢指针：slow 和 fast 从同侧出发，fast 走得快。适合链表和原地操作。
• 归并指针：分别指向两个有序序列，同步推进。适合合并、交集问题。

双指针能把很多 O(n²) 暴力解优化到 O(n)，是面试中最常考的技巧。

2. 核心模板

对撞指针（反转 + 回文判断）

// 判断回文数组
func isPalindrome(_ arr: [Int]) -> Bool {
    var left = 0, right = arr.count - 1
    while left < right {
        if arr[left] != arr[right] { return false }
        left += 1
        right -= 1
    }
    return true
}

快慢指针（原地移除元素）

// 移除所有值为 val 的元素，返回新长度
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
    var slow = 0
    for fast in 0..<nums.count {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow += 1
        }
    }
    return slow
}

复杂度

• 时间：O(n)
• 空间：O(1)

3. 经典题目精讲

LeetCode 283 · 移动零

题意：将数组中所有 0 移到末尾，保持非零元素相对顺序，原地操作。

思路：快慢指针，slow 指向下一个非零应放的位置。

func moveZeroes(_ nums: inout [Int]) {
    var slow = 0
    for fast in 0..<nums.count {
        if nums[fast] != 0 {
            nums.swapAt(slow, fast)
            slow += 1
        }
    }
}

LeetCode 167 · 两数之和 II

题意：给定有序数组和目标值，找两个数之和等于目标，返回下标（1-indexed）。

思路：对撞指针，和太小移左指针，和太大移右指针。

func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
    var left = 0, right = numbers.count - 1
    while left < right {
        let sum = numbers[left] + numbers[right]
        if sum == target {
            return [left + 1, right + 1]
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    return []
}

LeetCode 344 · 反转字符串

题意：原地反转字符数组。

思路：对撞指针交换。

func reverseString(_ s: inout [Character]) {
    var left = 0, right = s.count - 1
    while left < right {
        s.swapAt(left, right)
        left += 1
        right -= 1
    }
}

LeetCode 977 · 有序数组的平方

题意：给定非递减有序数组（含负数），返回每个元素平方后的有序数组。

思路：平方后最大值一定在两端，对撞指针从大到小填入结果。

func sortedSquares(_ nums: [Int]) -> [Int] {
    let n = nums.count
    var result = [Int](repeating: 0, count: n)
    var left = 0, right = n - 1
    var pos = n - 1
    while left <= right {
        let leftSq = nums[left] * nums[left]
        let rightSq = nums[right] * nums[right]
        if leftSq > rightSq {
            result[pos] = leftSq
            left += 1
        } else {
            result[pos] = rightSq
            right -= 1
        }
        pos -= 1
    }
    return result
}

4. 易错点

• ⚠️ 对撞指针循环条件是 left < right 还是 left <= right 取决于题意
• ⚠️ 快慢指针中 slow 的语义要明确——是"已处理区间的末尾"还是"待处理区间的开头"
• ⚠️ 交换 vs 覆盖：移除元素用覆盖，移动零用交换

5. 推荐刷题清单

题号	题名	难度	关键
167	两数之和 II	Medium	对撞指针
283	移动零	Easy	快慢指针
344	反转字符串	Easy	对撞指针
345	反转元音字母	Easy	对撞指针
977	有序数组的平方	Easy	对撞指针

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)