双指针算法详解：从入门到精通（Java版）

目录一、什么是双指针1.1 对撞指针左右指针1.2 快慢指针龟兔赛跑算法二、经典题目实战2.1 移动零LeetCode 2832.2 复写零LeetCode 10892.3 快乐数LeetCode 2022.4 盛水最多的容器LeetCode 112.5 有效三角形的个数LeetCode 6112.6 和为s的两个数字剑指Offer 572.7 三数之和LeetCode 152.8 四数之和LeetCode 18三、双指针算法总结一、什么是双指针双指针是一种常用的算法技巧通过使用两个指针在数组或链表等数据结构上进行移动来解决特定问题。根据指针移动方式的不同双指针主要分为两种形式1.1 对撞指针左右指针对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼近。终止条件left right两个指针指向同一个位置left right两个指针错开1.2 快慢指针龟兔赛跑算法快慢指针使用两个移动速度不同的指针在序列结构上移动。通常在一次循环中慢指针每次移动一位快指针每次移动两位。适用场景处理环形链表或数组研究出现循环往复的问题二、经典题目实战2.1 移动零LeetCode 283题目描述给定一个数组nums将所有 0 移动到数组末尾同时保持非零元素的相对顺序。算法思路使用两个指针cur和destcur用于遍历数组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]区间全为非零元素[dest1, 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 ListListInteger threeSum(int[] nums) { ListListInteger 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 ListListInteger fourSum(int[] nums, int target) { ListListInteger 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; } }三、双指针算法总结题目指针类型关键技巧移动零快慢指针数组分块维护非零区间复写零前后指针从后向前避免覆盖快乐数快慢指针检测循环盛水容器对撞指针移动较短边界三角形个数对撞指针排序后固定最长边两数之和对撞指针利用有序性三数之和对撞指针固定一个数去重四数之和对撞指针固定两个数去重双指针的核心思想通过分析问题的二段性利用指针移动来减少不必要的枚举将时间复杂度从 O(n²) 优化到 O(n)。使用技巧对撞指针常用于有序数组或字符串快慢指针常用于环形结构或需要检测循环的场景注意边界条件和指针移动的时机涉及去重问题时注意跳过重复元素