引言
双指针技巧是算法面试和竞赛中出现频率最高的技巧之一。它通过维护两个指针协同遍历数据结构，将许多看似需要 O(n²) 复杂度的问题优化到 O(n)。本文将用 Java 深入讲解双指针的两大经典变体——对撞指针与快慢指针，并通过多个经典问题展示其强大的解题能力。
双指针技巧概述
双指针的核心思想是利用问题的有序性或特定结构特征，让两个指针以不同策略移动，从而减少不必要的比较和遍历。
双指针主要分为两类：
– 对撞指针（Two Pointers）：两个指针从数组两端向中间移动，常用于有序数组的查找与配对问题
– 快慢指针（Fast & Slow Pointers）：两个指针以不同速度移动，常用于链表环检测、寻找中点等问题
对撞指针经典应用
两数之和 II（有序数组）
给定一个已按升序排列的整数数组，找出两个数使它们的和等于目标值。
核心思路：左指针指向数组开头（最小值），右指针指向数组末尾（最大值）。根据两数之和与目标值的大小关系移动指针：和太小则左指针右移，和太大则右指针左移。
import java.util.Arrays;
/**
* 两数之和 II — 对撞指针解法
* 时间复杂度：O(n) — 每个元素最多被访问一次
* 空间复杂度：O(1) — 仅使用两个指针
*
* @param numbers 已按升序排列的数组
* @param target 目标和
* @return 两个数的下标（从1开始计数）
*/
public int[] twoSum(int[] numbers, int target) {
int left = 0; // 左指针从数组开头出发
int right = numbers.length - 1; // 右指针从数组末尾出发
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 找到目标组合，返回结果（题目要求下标从1开始）
return new int[]{left + 1, right + 1};
} else if (sum < target) {
// 当前和太小，需要更大的数，左指针右移
left++;
} else {
// 当前和太大，需要更小的数，右指针左移
right--;
}
}
return new int[]{-1, -1}; // 题目保证有解，此行理论上不会执行
}
三数之和
给定一个整数数组，找出所有和为 0 的三元组，且三元组中不能有重复元素。
核心思路：先对数组排序，然后固定第一个数，对剩余部分使用对撞指针寻找两数之和等于目标值的组合。通过跳过重复元素来避免结果重复。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 三数之和 — 排序 + 对撞指针
* 时间复杂度：O(n²) — 外层固定一个数 O(n)，内层对撞指针 O(n)
* 空间复杂度：O(1) — 不包括存储结果的空间
*
* @param nums 整数数组
* @return 所有和为0的不重复三元组
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
// 先对数组排序，这是使用对撞指针的前提
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 跳过重复的第一个数，避免结果重复
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 如果当前最小三数之和大于0，后续不可能有解
if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
// 如果当前最大三数之和小于0，需要更大的第一个数
if (nums[i] + nums[nums.length - 2] + nums[nums.length - 1] < 0) continue;
int target = -nums[i]; // 需要寻找的两数之和
int left = i + 1; // 左指针从 i 的下一个位置出发
int right = nums.length - 1;
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;
}
盛最多水的容器
给定 n 条垂线，找出两条线使得它们与 x 轴构成的容器能容纳最多的水。
核心思路：对撞指针从两端出发，每次移动高度较小的一边。因为容器的盛水量由较短的边决定，移动较高的边不可能获得更大的面积。
/**
* 盛最多水的容器 — 对撞指针贪心策略
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*
* @param height 各垂线的高度数组
* @return 最大盛水量
*/
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
// 计算当前左右指针构成的容器面积
// 面积 = 宽度 * 高度，高度取两边中的较小值
int width = right - left;
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, width * h);
// 移动高度较小的一边：因为宽度在减小，只有可能通过增加高度来获得更大面积
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
快慢指针经典应用
链表环检测（Floyd 判圈算法）
判断链表中是否存在环，若存在则找出环的入口节点。
核心思路：慢指针每次移动一步，快指针每次移动两步。如果存在环，快指针最终会追上慢指针；如果不存在环，快指针会先到达链表末尾。
/**
* 链表节点定义
*/
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
/**
* 检测链表是否有环 — Floyd 判圈算法
* 时间复杂度：O(n) — 无环时快指针遍历完链表；有环时两指针在环内相遇
* 空间复杂度：O(1) — 仅使用两个指针
*
* @param head 链表头节点
* @return 是否存在环
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head; // 慢指针：每次移动一步
ListNode fast = head; // 快指针：每次移动两步
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针前进一步
fast = fast.next.next; // 快指针前进两步
if (slow == fast) {
// 快慢指针相遇，说明存在环
return true;
}
}
// 快指针到达链表末尾，说明无环
return false;
}
/**
* 寻找环的入口节点
* 数学证明：设链表头到环入口距离为 a，环入口到相遇点距离为 b，
* 相遇点回到环入口距离为 c。则 2(a+b) = a+b+c+b，可得 a = c。
* 因此让一个指针从头出发，另一个从相遇点出发，每次各走一步，
* 相遇处即为环入口。
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
// 第一阶段：判断是否有环，并找到相遇点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 第二阶段：寻找环的入口
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr; // 环的入口节点
}
}
return null; // 无环
}
寻找重复数
给定一个包含 n+1 个整数的数组，每个整数都在 1 到 n 之间（含），证明至少存在一个重复数。假设只有一个重复的整数，找出这个重复的数。
核心思路：将数组看作一个链表，下标作为节点值，数组值作为 next 指针。由于有重复数，这个”链表”必然存在环，问题转化为寻找环的入口。
/**
* 寻找重复数 — 将数组视为链表，使用 Floyd 判圈算法
* 时间复杂度：O(n)
* 空间复杂度：O(1) — 不修改数组，不使用额外空间
*
* @param nums 包含 n+1 个整数的数组，整数范围 [1, n]
* @return 重复的数字
*/
public int findDuplicate(int[] nums) {
// 将数组视为链表：索引 i 的 next 指向 nums[i]
// 由于存在重复值，必然形成环
int slow = nums[0]; // 慢指针从第一个元素出发
int fast = nums[nums[0]]; // 快指针从第二个元素出发
// 第一阶段：寻找相遇点
while (slow != fast) {
slow = nums[slow]; // 慢指针前进一步
fast = nums[nums[fast]]; // 快指针前进两步
}
// 第二阶段：寻找环入口（即重复数）
int ptr = 0;
while (ptr != slow) {
ptr = nums[ptr];
slow = nums[slow];
}
return ptr; // 重复的数字
}
删除链表的倒数第 N 个节点
核心思路：快指针先前进 N 步，然后快慢指针同步前进。当快指针到达链表末尾时，慢指针正好位于倒数第 N 个节点的前一个位置。
/**
* 删除链表的倒数第 N 个节点 — 快慢指针
* 时间复杂度：O(n) — 只需遍历链表一次
* 空间复杂度：O(1)
*
* @param head 链表头节点
* @param n 倒数第 n 个
* @return 删除后的链表头节点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 使用虚拟头节点，简化删除头节点的边界情况处理
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// 快指针先前进 n+1 步，使快慢指针之间保持 n 个节点的距离
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 快慢指针同步前进，直到快指针到达链表末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// slow 此时指向倒数第 n 个节点的前一个节点
slow.next = slow.next.next;
return dummy.next;
}
双指针解题框架总结
/**
* 对撞指针通用模板
* 适用于：有序数组查找、配对问题
*/
public void twoPointersTemplate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// 根据题目逻辑处理 nums[left] 和 nums[right]
// ...
// 移动指针的策略取决于题目要求
if (shouldMoveLeft(nums[left], nums[right])) {
left++;
} else {
right--;
}
}
}
/**
* 快慢指针通用模板
* 适用于：链表环检测、寻找中点、删除倒数第N个节点
*/
public void fastSlowTemplate(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针前进一步
fast = fast.next.next; // 快指针前进两步
// 检查是否相遇或满足其他终止条件
// ...
}
}
复杂度分析
| 问题 | 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 两数之和 II | 对撞指针 | O(n) | O(1) |
| 三数之和 | 排序 + 对撞指针 | O(n²) | O(1) |
| 盛最多水的容器 | 对撞指针贪心 | O(n) | O(1) |
| 链表环检测 | Floyd 判圈 | O(n) | O(1) |
| 寻找重复数 | Floyd 判圈 | O(n) | O(1) |
| 删除倒数第 N 个节点 | 快慢指针 | O(n) | O(1) |
总结
双指针技巧的魅力在于它用极其简洁的代码和 O(1) 的额外空间解决了许多复杂问题。对撞指针利用了数据的有序性，通过两端向中间的夹逼策略缩小搜索范围；快慢指针则利用了指针速度差来发现链表中的结构特征。掌握这两种双指针模式，能够帮助你快速识别并解决大量算法问题。在实际编程中，养成先思考”能否使用双指针”的习惯，往往能事半功倍。
