尺取法（双指针法）详解：原理、应用与实战

1. 什么是尺取法

尺取法（Two Pointers），又称双指针法，是一种在数组或链表等线性数据结构上通过两个指针（索引）协同遍历来高效解决问题的算法技巧。其核心思想是：维护一个区间（窗口），通过移动左右指针来动态调整区间范围，从而避免暴力枚举，将时间复杂度从 O(n²) 降低到 O(n)。

形象地说，就像用一把可以伸缩的尺子在数据上滑动测量，因此得名“尺取法”。

2. 尺取法的适用场景

尺取法通常适用于以下类型的问题：

• 连续子数组/子串问题：寻找满足某种条件（如和、乘积、字符种类等）的最短/最长连续子区间。
• 有序数组的两数之和/三数之和：利用数组有序性，通过左右指针向中间逼近。
• 去重或合并有序数组：需要在线性时间内完成去重或合并操作。
• 滑动窗口最大值/最小值：通常结合单调队列使用，但指针移动逻辑类似。

一个关键前提是：当右指针向右移动时，区间的某个属性（如和、乘积）是单调变化的，这样左指针的移动才有意义。

3. 算法框架与模板

尺取法的通用代码框架（以寻找和大于等于 target 的最短连续子数组为例）如下：

public int minSubArrayLen(int target, int[] nums) { int left = 0; // 左指针 int sum = 0; // 当前窗口的和 int minLen = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; // 右指针扩张，加入新元素 // 当窗口满足