什么是双指针技术？

Question

什么是双指针技术？

IT Interview Practice · Accepted Answer

**双指针** 技术使用两个索引在序列中移动，以单次扫描解决问题 — 将许多 O(n²) 的暴力解决方案转变为 **O(n)**。

## 核心思想

保持两个指针（通常在两端，或一个慢一个快），根据条件移动它们，缩小工作范围而无需重新扫描。

## 示例：在有序数组中找到和为目标值的配对

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## 复杂度

- **时间:** O(n)。**空间:** O(1)。

## 何时使用 / 注意事项

非常适合 **有序数组**、回文检查、反转和原地去重。对于收敛指针变种，数组通常需要有序。注意指针边界和循环条件（`lo < hi`）。

## 为什么这很重要

双指针是面试中高价值的技巧之一：它将嵌套循环简化为一次清晰的线性扫描。

它教会你利用结构（如有序性）而非暴力破解。

同样的思想驱动着合并、分区和归并排序的合并步骤。

核心思想

示例：在有序数组中找到和为目标值的配对

相关问题

复杂度

何时使用 / 注意事项

为什么这很重要