双指针算法详解：从入门到精通（Java版）-平芜编程栈

一、什么是双指针？

1.1 对撞指针（左右指针）

1.2 快慢指针（龟兔赛跑算法）

二、经典题目实战

2.1 移动零（LeetCode 283）

2.2 复写零（LeetCode 1089）

2.3 快乐数（LeetCode 202）

2.4 盛水最多的容器（LeetCode 11）

2.5 有效三角形的个数（LeetCode 611）

2.6 和为s的两个数字（剑指Offer 57）

2.7 三数之和（LeetCode 15）

2.8 四数之和（LeetCode 18）

三、双指针算法总结

一、什么是双指针？

双指针是一种常用的算法技巧，通过使用两个指针在数组或链表等数据结构上进行移动，来解决特定问题。根据指针移动方式的不同，双指针主要分为两种形式：

1.1 对撞指针（左右指针）

对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。

终止条件：

left == right：两个指针指向同一个位置
left > right：两个指针错开

1.2 快慢指针（龟兔赛跑算法）

快慢指针使用两个移动速度不同的指针在序列结构上移动。通常在一次循环中，慢指针每次移动一位，快指针每次移动两位。

适用场景：

处理环形链表或数组
研究出现循环往复的问题

二、经典题目实战

2.1 移动零（LeetCode 283）

题目描述：给定一个数组nums，将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。

算法思路：

使用两个指针cur和dest，cur用于遍历数组，dest指向非零元素序列的最后一个位置。

class Solution { public void moveZeroes(int[] nums) { for (int cur = 0, dest = -1; cur < nums.length; cur++) { if (nums[cur] != 0) { // 处理非零元素 dest++; int temp = nums[dest]; nums[dest] = nums[cur]; nums[cur] = temp; } } } }

核心思想：遍历过程中，使[0, dest]区间全为非零元素，[dest+1, cur-1]区间全为零。

2.2 复写零（LeetCode 1089）

题目描述：将数组中每个零都复写一遍，其余元素向右平移，不能超过数组长度。

算法思路：

采用"从后向前"的复写策略，避免从前向后复写时数据被覆盖。

class Solution { public void duplicateZeros(int[] arr) { int cur = 0, dest = -1, n = arr.length; // 1. 先找到最后一个需要复写的数 while (cur < n) { if (arr[cur] == 0) { dest += 2; } else { dest += 1; } if (dest >= n - 1) break; cur++; } // 2. 处理边界情况 if (dest == n) { arr[n - 1] = 0; cur--; dest -= 2; } // 3. 从后向前完成复写操作 while (cur >= 0) { if (arr[cur] != 0) { arr[dest--] = arr[cur--]; } else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } }

2.3 快乐数（LeetCode 202）

题目描述：判断一个数是否为快乐数。快乐数定义为：每次将该数替换为它每个位置上的数字的平方和，重复这个过程直到变为1，或进入无限循环。

算法思路：

使用快慢指针检测循环。如果相遇位置的值是1，则是快乐数；否则不是。

class Solution { public boolean isHappy(int n) { int slow = n, fast = bitSum(n); while (slow != fast) { slow = bitSum(slow); fast = bitSum(bitSum(fast)); } return slow == 1; } private int bitSum(int n) { int sum = 0; while (n != 0) { int t = n % 10; sum += t * t; n /= 10; } return sum; } }

2.4 盛水最多的容器（LeetCode 11）

题目描述：找出两条垂线，使它们与x轴构成的容器能容纳最多的水。

算法思路：

使用对撞指针，每次移动较短的边界，因为移动较长边界只会使容积变小。

class Solution { public int maxArea(int[] height) { int left = 0, right = height.length - 1, ret = 0; while (left < right) { int v = Math.min(height[left], height[right]) * (right - left); ret = Math.max(ret, v); if (height[left] < height[right]) { left++; } else { right--; } } return ret; } }

2.5 有效三角形的个数（LeetCode 611）

题目描述：返回数组中可以组成三角形三条边的三元组个数。

算法思路：

先排序，固定最长边，使用对撞指针在剩余区间中寻找满足两边之和大于第三边的组合。

class Solution { public int triangleNumber(int[] nums) { // 1. 排序 Arrays.sort(nums); // 2. 利用双指针解决问题 int ret = 0, n = nums.length; for (int i = n - 1; i >= 2; i--) { // 固定最大的数 int left = 0, right = i - 1; while (left < right) { if (nums[left] + nums[right] > nums[i]) { ret += right - left; right--; } else { left++; } } } return ret; } }

2.6 和为s的两个数字（剑指Offer 57）

题目描述：在递增排序的数组中查找两个数，使它们的和等于目标值。

算法思路：

利用数组有序的特性，使用对撞指针，根据当前和与目标值的大小关系移动指针。

class Solution { public int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { return new int[]{nums[left], nums[right]}; } } return new int[]{-1, -1}; } }

2.7 三数之和（LeetCode 15）

题目描述：找出数组中所有和为0且不重复的三元组。

算法思路：

先排序，固定一个数，在其后的区间中使用双指针找两数之和等于目标值，注意去重。

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret = new ArrayList<>(); // 1. 排序 Arrays.sort(nums); // 2. 利用双指针解决问题 int n = nums.length; for (int i = 0; i < n; ) { // 固定数 a if (nums[i] > 0) break; // 小优化 int left = i + 1, right = n - 1, target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { ret.add(Arrays.asList(nums[i], nums[left], nums[right])); left++; right--; // 去重操作 while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // 去重 i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } }

2.8 四数之和（LeetCode 18）

题目描述：找出数组中所有和为target且不重复的四元组。

算法思路：

在三数之和的基础上再套一层循环，固定两个数，使用双指针找剩余两数。

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ret = new ArrayList<>(); // 1. 排序 Arrays.sort(nums); // 2. 利用双指针解决问题 int n = nums.length; for (int i = 0; i < n; ) { // 固定数 a for (int j = i + 1; j < n; ) { // 固定数 b int left = j + 1, right = n - 1; long aim = (long)target - nums[i] - nums[j]; while (left < right) { int sum = nums[left] + nums[right]; if (sum > aim) { right--; } else if (sum < aim) { left++; } else { ret.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); left++; right--; // 去重 while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // 去重 j++; while (j < n && nums[j] == nums[j - 1]) j++; } // 去重 i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } }

三、双指针算法总结

题目	指针类型	关键技巧
移动零	快慢指针	数组分块，维护非零区间
复写零	前后指针	从后向前避免覆盖
快乐数	快慢指针	检测循环
盛水容器	对撞指针	移动较短边界
三角形个数	对撞指针	排序后固定最长边
两数之和	对撞指针	利用有序性
三数之和	对撞指针	固定一个数+去重
四数之和	对撞指针	固定两个数+去重