假设你面前有一组从小到大排好序的数字，需要找出其中任意两个数之和等于目标值的组合。最直观的想法是嵌套两层循环，逐一尝试所有配对——时间复杂度 $O(n^2)$，当数据量达到十万级别时，程序开始变得迟缓。
但如果换一个思路：让一个指针从数组开头出发，另一个从末尾出发，根据当前两数之和与目标值的大小关系，决定移动哪个指针。这种策略只需要一次遍历就能找到答案，时间复杂度骤降至 $O(n)$。这就是双指针算法的核心魅力——用两个变量同时追踪不同位置，将嵌套循环降维成单层扫描。
双指针算法的本质
双指针（Two Pointers）是一种在数组、字符串或链表等线性结构上进行高效遍历的技术。它通过维护两个指向不同位置的指针，利用它们之间的相对位置关系来优化搜索过程。这种技术能将原本需要 $O(n^2)$ 甚至更高复杂度的暴力解法，优化到 $O(n)$ 级别。
双指针算法之所以高效，关键在于利用数据的有序性或特定结构来剪枝。当数组有序时，我们可以根据当前状态排除大量不可能的候选解，避免无效搜索。而当处理链表问题时，双指针可以在不借助额外空间的情况下，完成周期检测、中点查找等操作。
图片来源: LeetCode Discuss
根据指针移动方向和速度的差异，双指针可以分为三种主要类型。
相向双指针：从两端向中间靠拢
相向双指针也称为对撞指针，两个指针分别从数组的两端出发，根据特定条件向中间移动。这种模式最适合处理有序数组中的配对问题。
LeetCode 167. Two Sum II - Input Array Is Sorted
这是相向双指针最经典的应用场景。
题目描述：给定一个已按升序排列的整数数组 numbers 和一个目标值 target，找出数组中两个数，使它们的和等于目标值。返回这两个数的索引（从1开始计数）。
解题思路：由于数组有序，设左指针 left 指向开头，右指针 right 指向末尾。若 numbers[left] + numbers[right] 小于目标值，说明需要更大的数，left 右移；若大于目标值，说明需要更小的数，right 左移。直到找到答案或两指针相遇。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1}; // 未找到
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。相比暴力法的 $O(n^2)$，效率提升了一个数量级。
LeetCode 11. Container With Most Water
题目描述：给定一个长度为 n 的整数数组 height，每个元素代表一条垂直线的高度。找出两条线，使它们与 x 轴共同构成的容器可以容纳最多的水。
解题思路：容器的容量由两条线之间的距离和较短线的高度决定。使用相向双指针，初始时 left 在最左，right 在最右。计算当前容量后，移动较矮的那条线对应的指针——因为只有换一条更高的线，才可能获得更大的容量。
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
int width = right - left;
int h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, width * h);
// 移动较矮的指针
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。
LeetCode 15. 3Sum
题目描述：找出数组中所有和为 0 的三元组，要求不重复。
解题思路：先对数组排序。固定第一个数 nums[i]，然后在剩余区间 [i+1, n-1] 上使用相向双指针寻找两数之和等于 -nums[i] 的组合。需要注意去重。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 跳过重复的第一个数
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复元素
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}
复杂度分析：排序 $O(n \log n)$，双指针遍历 $O(n^2)$，总体 $O(n^2)$。
LeetCode 42. Trapping Rain Water
题目描述：给定一个非负整数数组表示柱子的高度图，计算下雨后能接多少雨水。
解题思路：对于位置 i，能接的雨水量取决于它左右两侧最高柱子中较矮的那个，减去当前柱子高度。可以使用相向双指针优化空间复杂度：维护 leftMax 和 rightMax 分别记录左右两侧已遍历过的最大高度，根据哪一侧的最大值较小来决定处理哪一侧。
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。
LeetCode 125. Valid Palindrome
题目描述：判断一个字符串是否是回文串，只考虑字母和数字，忽略大小写。
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// 跳过非字母数字字符
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
// 比较字符（忽略大小写）
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}
LeetCode 75. Sort Colors (Dutch National Flag)
题目描述：对包含 0、1、2 三种颜色的数组进行排序，要求一次遍历完成。
解题思路：这是一个三指针变种。使用 low、mid、high 三个指针将数组分为四个区域：[0, low-1] 存放 0，[low, mid-1] 存放 1，[mid, high] 是待处理区域，[high+1, n-1] 存放 2。
class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums, low, mid);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
swap(nums, mid, high);
high--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。
快慢指针：同起点不同速度
快慢指针是双指针的一个重要变种，两个指针从同一位置出发，但移动速度不同。通常快指针每次移动两步，慢指针每次移动一步。这种模式特别适合处理链表问题。
LeetCode 141. Linked List Cycle
题目描述：判断链表是否有环。
解题思路：快指针每次走两步，慢指针每次走一步。如果有环，快指针最终会追上慢指针；如果无环，快指针会先到达链表末尾。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。相比于使用哈希表的 $O(n)$ 空间解法，快慢指针实现了常数空间。
LeetCode 142. Linked List Cycle II
题目描述：找出链表环的入口节点。
解题思路：第一阶段用快慢指针判断是否有环并找到相遇点。第二阶段，将一个指针重新指向链表头，两个指针以相同速度前进，相遇点即为环的入口。
数学推导：设链表头到环入口距离为 $x$，环入口到相遇点距离为 $y$，相遇点到环入口距离为 $z$。快指针走过的距离是慢指针的两倍：$2(x + y) = x + y + n(y + z)$，化简得 $x = (n-1)(y+z) + z$。这意味着从头节点出发和从相遇点出发的指针，以相同速度前进会在环入口相遇。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// 第一阶段：检测是否有环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 第二阶段：找环入口
ListNode start = head;
while (start != slow) {
start = start.next;
slow = slow.next;
}
return start;
}
}
return null;
}
}
LeetCode 876. Middle of the Linked List
题目描述：找出链表的中间节点。如果有两个中间节点，返回第二个。
解题思路：快指针走到末尾时，慢指针正好在中间。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
LeetCode 19. Remove Nth Node From End of List
题目描述：删除链表的倒数第 n 个节点。
解题思路：让快指针先走 n 步，然后快慢指针同时前进。当快指针到达末尾时，慢指针正好指向倒数第 n 个节点的前一个节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
// 快指针先走 n 步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 同时前进
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 删除节点
slow.next = slow.next.next;
return dummy.next;
}
}
LeetCode 287. Find the Duplicate Number
题目描述：在包含 $n+1$ 个整数的数组中，所有数都在 $[1, n]$ 范围内，找出唯一的重复数。要求不修改数组，使用 $O(1)$ 额外空间。
解题思路：这道题可以将数组视为链表——值 nums[i] 表示从节点 i 指向节点 nums[i]。由于存在重复值，这条"链表"必有环。问题转化为找环的入口。
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
// 检测环
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 找环入口
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(1)$。
同向双指针：滑动窗口的原型
同向双指针中，两个指针从同一方向出发，通常一个指针负责探索，另一个指针负责标记边界。这种模式是滑动窗口算法的基础。
LeetCode 26. Remove Duplicates from Sorted Array
题目描述：原地删除有序数组中的重复元素，返回新长度。
解题思路：slow 指针指向当前不重复序列的末尾，fast 指针负责遍历。当 nums[fast] 与 nums[slow] 不同时，将 slow 前进并赋值。
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
}
LeetCode 283. Move Zeroes
题目描述：将数组中的所有 0 移到末尾，保持非零元素相对顺序。
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0; // 指向下一个非零元素应该放置的位置
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
}
// 填充剩余的 0
while (slow < nums.length) {
nums[slow] = 0;
slow++;
}
}
}
LeetCode 3. Longest Substring Without Repeating Characters
题目描述：找出不含重复字符的最长子串长度。
解题思路：使用哈希集合维护窗口内的字符。right 指针扩展窗口，遇到重复字符时 left 指针收缩窗口。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 收缩窗口直到无重复
while (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}
window.add(c);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
复杂度分析：时间复杂度 $O(n)$，虽然有两层循环，但每个字符最多被访问两次。空间复杂度 $O(\min(m, n))$，其中 $m$ 是字符集大小。
总结与使用场景判断
双指针算法的核心在于根据问题特征选择合适的指针移动策略：
| 指针类型 | 适用场景 | 典型问题 |
|---|---|---|
| 相向双指针 | 有序数组的配对问题、回文判断 | Two Sum II、Container With Most Water、Valid Palindrome |
| 快慢指针 | 链表环检测、中点查找、周期检测 | Linked List Cycle、Middle of Linked List、Find Duplicate |
| 同向双指针 | 原地修改数组、滑动窗口 | Remove Duplicates、Move Zeroes、Longest Substring |
判断是否可以使用双指针的关键条件：
- 相向双指针：数据是否有序？是否在寻找配对？
- 快慢指针：是否涉及链表？是否需要检测周期性？
- 同向双指针：是否需要维护一个动态窗口？是否可以原地修改？
双指针算法的魅力在于它的简洁与高效——往往只需要几行代码，就能将暴力解法的时间复杂度降低一个数量级。掌握这三类模式及其变体，足以应对绝大多数面试场景中的双指针题目。