1. 概述
本文将介绍双指针（Two Pointer）技巧在数组和链表问题中的应用。这是一种简单且高效的优化手段，能显著提升算法性能。
2. 技巧说明
在处理数组或列表相关的问题时，我们常常需要将数组中的每个元素与其他元素进行比较分析。
通常我们会从索引 0 开始，通过一层或多层循环遍历数组。有时为了满足特定需求，还需要创建临时数组。
虽然这种暴力方式可以解决问题，但往往不是最节省时间和空间的方案。
因此，在面对这类问题时，不妨考虑是否可以通过 双指针技巧 来提高效率。
在双指针方法中，“指针”指的是数组的索引位置。借助两个指针，我们可以在一次循环中同时处理两个元素，而不是只处理一个。
常见的双指针模式包括：
- 两个指针分别从数组的起始和末尾出发，向中间移动，直到相遇
- 一个指针移动速度较慢，另一个较快（快慢指针）
这两种模式都能帮助我们在更少的迭代次数下得出结果，并且不需要额外的空间开销，从而有效降低 时间与空间复杂度。
接下来，我们通过几个经典例子来深入理解这一技巧。
3. 判断数组中是否存在两数之和等于目标值
问题描述：
给定一个已排序的整型数组，判断其中是否存在两个数字的和等于某个目标值。
例如：输入数组为 [1, 1, 2, 3, 4, 6, 8, 9]，目标值为 11，则应返回 true；若目标值为 20，则返回 false。
常规解法 ❌
public boolean twoSumSlow(int[] input, int targetValue) {
for (int i = 0; i < input.length; i++) {
for (int j = 1; j < input.length; j++) {
if (input[i] + input[j] == targetValue) {
return true;
}
}
}
return false;
}
这个解法使用了嵌套循环，时间复杂度为 ✅ **O(n²)**。
双指针优化 ✅
public boolean twoSum(int[] input, int targetValue) {
int pointerOne = 0;
int pointerTwo = input.length - 1;
while (pointerOne < pointerTwo) {
int sum = input[pointerOne] + input[pointerTwo];
if (sum == targetValue) {
return true;
} else if (sum < targetValue) {
pointerOne++;
} else {
pointerTwo--;
}
}
return false;
}
由于数组已经有序，我们可以设置两个指针：
- 左指针指向数组开头
- 右指针指向数组末尾
每次计算两个指针对应元素的和：
- 如果和小于目标值，则左指针右移
- 如果和大于目标值，则右指针左移
- 直到找到匹配值或两指针相遇
✅ 时间复杂度优化为 O(n)
✅ 空间复杂度为 O(1)
相比暴力解法，效率提升明显。
4. 数组向右旋转 k 步
问题描述：
给定一个数组，将其向右旋转 k 步（k 非负）。
例如：数组 [1, 2, 3, 4, 5, 6, 7]，k = 4，则输出应为 [4, 5, 6, 7, 1, 2, 3]。
常规思路 ❌
- 使用双重循环：时间复杂度 O(n²)
- 使用额外数组：空间复杂度 O(n)
双指针翻转法 ✅
public void rotate(int[] input, int step) {
step %= input.length;
reverse(input, 0, input.length - 1);
reverse(input, 0, step - 1);
reverse(input, step, input.length - 1);
}
private void reverse(int[] input, int start, int end) {
while (start < end) {
int temp = input[start];
input[start] = input[end];
input[end] = temp;
start++;
end--;
}
}
该方法利用双指针实现原地翻转：
- 先整体翻转数组
- 再翻转前 k 个元素
- 最后翻转剩下的元素
✅ 时间复杂度为 O(n)
✅ 空间复杂度为 O(1)
5. 找出单向链表的中间节点
问题描述：
给定一个单向链表，找出它的中间节点。
例如：链表为 1->2->3->4->5，中间节点应为 3。
快慢指针法 ✅
public <T> T findMiddle(MyNode<T> head) {
MyNode<T> slowPointer = head;
MyNode<T> fastPointer = head;
while (fastPointer.next != null && fastPointer.next.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
}
return slowPointer.data;
}
使用两个指针遍历链表：
- 慢指针每次走一步
- 快指针每次走两步
当快指针到达链表末尾时，慢指针正好位于中间位置。
✅ 时间复杂度为 O(n)
✅ 空间复杂度为 O(1)
6. 总结
本文通过多个实际案例展示了双指针技巧的强大之处：
- ✅ 适用于数组、链表等线性结构
- ✅ 能有效降低时间和空间复杂度
- ✅ 实现简单，逻辑清晰，是面试高频考点
掌握好这个技巧，能让你在刷题或实际开发中事半功倍。