数组的高级应用：双指针技巧
引言
在算法和数据结构中，双指针（Two Pointers）是一种高效的技术，常用于解决涉及数组或链表的问题。它通过使用两个指针在数组或链表上移动，巧妙地降低了时间复杂度，提高了算法效率。
一、单指针的局限性
1. 概述
- 单指针：指在遍历数组或链表时，只使用一个指针（索引）从头到尾（或从尾到头）依次访问元素。
2. 局限性
无法同时处理多个位置的元素：单指针一次只能访问一个位置的元素，无法同时处理数组中不同位置的元素之间的关系。
效率低下：在需要比较或处理数组中多个元素之间的关系时，使用单指针可能需要嵌套循环，导致时间复杂度增高到 O(n²)。
不适合某些特定问题：如在有序数组中查找两数之和为特定值的组合，使用单指针无法高效解决。
3. 示例
问题：在一个有序数组中，查找是否存在两个数之和等于目标值 target。
单指针解法：
public boolean twoSumSinglePointer(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int complement = target - nums[i];
// 线性搜索 complement
for (int j = i + 1; j < n; j++) {
if (nums[j] == complement) {
return true;
}
}
}
return false;
}
时间复杂度：O(n²)
二、双指针的优势
- 提高效率：通过同时移动两个指针，可以将一些需要 O(n²) 时间复杂度的问题优化为 O(n)。
- 空间高效：大多数双指针算法只需要 O(1) 的额外空间。
- 简化代码：双指针方法通常使代码更简洁、易读。
三、双指针的类型及应用场景
1. 快慢指针（同向双指针）
定义
- 慢指针（Slow Pointer）：移动速度较慢，每次移动一格。
- 快指针（Fast Pointer）：移动速度较快，每次移动多格（通常为两格）。
优势
- 效率提升：减少了不必要的元素移动和比较，降低时间复杂度。
- 空间节省：在原地进行操作，不需要额外的空间。
应用场景
- 删除排序数组中的重复项：在排序数组中，移除重复的元素，返回新的长度。
- 链表问题：如检测链表中的环、寻找链表的中间节点。
示例代码
问题：从排序数组中删除重复项，返回新长度，并在原数组上进行操作。
解法：使用快慢指针。
public class RemoveDuplicates {
public static 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; // 新数组长度
}
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 4, 4};
int length = removeDuplicates(nums);
System.out.println("新的长度: " + length);
System.out.print("更新后的数组: ");
for (int i = 0; i < length; i++) {
System.out.print(nums[i] + " ");
}
}
}
输出结果：
新的长度: 4
更新后的数组: 1 2 3 4
复杂度分析：
- 时间复杂度：O(n)，其中 n 为数组长度。快指针遍历整个数组一次。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
解释
-
慢指针
slow：指向已处理的数组的末尾位置，代表下一个可以填充新元素的位置。 -
快指针
fast：用于遍历数组，查找未处理的元素。 -
算法流程：
- 初始化慢指针
slow为 0。 - 快指针
fast从索引 1 开始遍历数组。 - 如果
nums[fast] != nums[slow]，说明找到新的元素：- 慢指针
slow前进一步。 - 将
nums[fast]的值赋给nums[slow]。
- 慢指针
- 最终，
slow + 1即为新数组的长度。
- 初始化慢指针
2. 左右指针（相向双指针）
定义
- 左指针（Left Pointer）：从数组的起始位置开始向右移动。
- 右指针（Right Pointer）：从数组的末尾位置开始向左移动。
优势
- 高效搜索：适用于有序数组，可在 O(n) 时间内解决许多需要 O(n²) 时间的搜索问题。
- 空间节省：无需额外的存储空间。
应用场景
- 两数之和：在有序数组中，找到两个数，使其和等于目标值。
- 判断回文串：验证字符串是否为回文。
示例代码
问题：在有序数组中，找到两个数，使其和等于目标值。
public class TwoSumSorted {
public static 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) {
return new int[]{left + 1, right + 1}; // 返回索引（从1开始）
} else if (sum < target) {
left++; // 左指针右移
} else {
right--; // 右指针左移
}
}
return new int[]{-1, -1}; // 未找到解
}
public static void main(String[] args) {
int[] numbers = {2, 3, 4, 7, 11, 15};
int target = 9;
int[] result = twoSum(numbers, target);
System.out.println("索引: " + result[0] + ", " + result[1]);
}
}
输出结果：
索引: 2, 3
复杂度分析：
- 时间复杂度：O(n)，n 为数组长度，每个元素最多访问一次。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
解释
-
左指针
left：从数组起始位置开始。 -
右指针
right：从数组末尾位置开始。 -
算法流程：
- 初始化左指针
left为 0，右指针right为数组最后一个索引。 - 计算当前指针所指元素之和
sum = numbers[left] + numbers[right]。 - 如果
sum == target，返回指针索引。 - 如果
sum < target，左指针右移left++。 - 如果
sum > target，右指针左移right--。 - 重复上述步骤，直到找到符合条件的两个数或指针交错。
- 初始化左指针
四、复杂度总结
快慢指针
- 时间复杂度：O(n)
- 空间复杂度：O(1)
左右指针
- 时间复杂度：O(n)
- 空间复杂度：O(1)
五、双指针的优势总结
- 高效性：将复杂度从 O(n²) 降低到 O(n)。
- 简洁性：代码更简洁，可读性更强。
- 空间效率：通常不需要额外的存储空间，原地操作。
六、注意事项
-
边界条件：注意指针初始化和移动时的边界，防止数组越界。
好的设计一般先判断临界条件 - 指针移动逻辑：根据问题需要，正确判断何时移动左指针、右指针、快指针或慢指针。
- 有序性要求：左右指针常用于有序数组或字符串，确保数据满足条件。
七、练习题推荐
- LeetCode 26. 删除排序数组中的重复项（快慢指针）
- LeetCode 283. 移动零（快慢指针）
- LeetCode 167. 两数之和 II - 输入有序数组（左右指针）
- LeetCode 125. 验证回文串（左右指针）
- LeetCode 680. 验证回文字符串 Ⅱ（左右指针）
