核心要点

  • 对撞指针：用于有序数组，左右指针向中间收缩，如两数之和、判回文、盛水容器

  • 快慢指针：一个走一步一个走两步，用于链表找中点、判环、原地去重

  • 复杂度：两个指针各遍历一次，时间 O(n)、空间 O(1)，关键是想清指针移动条件

标准回答

双指针是用两个索引在序列上协同移动来降低复杂度的技巧，主要分两类：对撞指针从两端向中间逼近，适合有序数组的两数之和、回文判断、接雨水等，通过比较当前和与目标决定移动哪一端；快慢指针让两个指针以不同速度前进，适合链表找中点、判断是否成环、数组原地去重。它能把许多暴力 O(n²) 解法优化到 O(n)。下面给出有序数组两数之和（对撞）和快慢指针找链表中点两个例子：

python
def two_sum_sorted(nums, target):
    # 对撞指针：nums 已升序排列
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1     # 和偏小，左指针右移增大
        else:
            right -= 1    # 和偏大，右指针左移减小
    return [-1, -1]


class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt


def middle_node(head):
    # 快慢指针：fast 走两步、slow 走一步，fast 到尾时 slow 在中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


if __name__ == '__main__':
    print(two_sum_sorted([2, 7, 11, 15], 9))   # [0, 1]
    # 链表 1->2->3->4->5，中点为 3
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    print(middle_node(head).val)                # 3

常见误区

⚠️ 常见踩坑

对撞指针要求数组有序，无序时需先排序或改用哈希；快慢指针的循环条件要写 fast and fast.next，否则偶数长度链表会空指针。

追问

追问 1：对撞指针为什么能保证不漏解？

因为数组有序：当 nums[left]+nums[right] < target 时，固定 right 配任何更小的左元素都更小，故 left 必须右移；反之 right 左移。每一步都安全排除一个不可能的端点，所以遍历一遍即可，时间 O(n)。

追问 2：链表长度为偶数时 middle_node 返回前中点还是后中点？

本写法返回靠后的中点（如 1->2->3->4 返回 3）。若想返回前中点，把循环条件改成 while fast.next and fast.next.next 即可。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题