双指针算法详细讲解

覆盖快慢指针、左右对撞指针、滑动窗口三类高频双指针场景，难度从入门到中等，面试常用。

前置说明

双指针两大核心类型：

例题1：有序数组两数之和（左右对撞）

题目

升序数组numbers，目标值target，返回两个下标（从1开始），两数相加=target，唯一解。
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length – 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left+1, right+1};
} else if (sum < target) {
left++;
} else {
right–;
}
}
return new int[]{};
}
例题2：移除元素（同向快慢指针）

题目

原地移除数组中等于val的元素，返回新长度，不能新开数组。
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
例题3：有序数组去重（快慢指针）

题目

升序数组原地删除重复元素，每个元素只保留1次，返回新长度。
public 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]){
nums[++slow] = nums[fast];
}
}
return slow+1;
}
例题4：反转数组（左右对撞）

题目

原地反转整型数组。
public void reverseArray(int[] nums) {
int l = 0, r = nums.length – 1;
while(l < r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
l++; r–;
}
}
例题5：回文字符串验证（左右指针）

题目

只看字母数字，忽略大小写、空格符号，判断是否回文。
public boolean isPalindrome(String s) {
char[] arr = s.toCharArray();
int l = 0, r = arr.length-1;
while(l < r){
while(l<r && !Character.isLetterOrDigit(arr[l])) l++;
while(l<r && !Character.isLetterOrDigit(arr[r])) r–;
if(Character.toLowerCase(arr[l]) != Character.toLowerCase(arr[r])){
return false;
}
l++; r–;
}
return true;
}
例题6：盛最多水的容器（左右贪心指针）

题目

高度数组，两垂线和x轴围成容器，求最大储水量。
public int maxArea(int[] height) {
int l = 0, r = height.length-1;
int max = 0;
while(l < r){
int w = r – l;
int h = Math.min(height[l], height[r]);
max = Math.max(max, w*h);
if(height[l] < height[r]) l++;
else r–;
}
return max;
}
例题7：三数之和（排序+左右对撞）

题目

nums数组，找出所有不重复三元组 a+b+c=0。
import java.util.*;
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
if(nums[i]>0) break;
if(i>0 && nums[i]nums[i-1]) continue;
int l = i+1, r = nums.length-1;
while(l<r){
int sum = nums[i]+nums[l]+nums[r];
if(sum0){
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(l<r && nums[l]==nums[l+1]) l++;
while(l<r && nums[r]==nums[r-1]) r–;
l++;r–;
}else if(sum<0) l++;
else r–;
}
}
return res;
}
例题8：移动零（快慢指针）

题目

数组所有0移到末尾，非零元素相对顺序不变，原地操作。
public void moveZeroes(int[] nums) {
int slow = 0;
for(int fast=0; fast<nums.length; fast++){
if(nums[fast] != 0){
int tmp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = tmp;
slow++;
}
}
}
例题9：链表倒数第N个节点（快慢指针）

链表节点定义
class ListNode{
int val; ListNode next;
ListNode(int x){val=x;}
}
解法

快指针先走n步，快慢同步后移，快到末尾慢就是倒数n节点：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for(int i=0;i<=n;i++) fast=fast.next;
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
例题10：长度最小的子数组（滑动窗口双指针）

题目

正整数数组nums，目标s，找连续子数组和≥s的最小长度，无则返回0。
public int minSubArrayLen(int s, int[] nums) {
int l=0, sum=0, minLen=Integer.MAX_VALUE;
for(int r=0; r<nums.length; r++){
sum += nums[r];
while(sum >= s){
minLen = Math.min(minLen, r-l+1);
sum -= nums[l++];
}
}
return minLen==Integer.MAX_VALUE ? 0 : minLen;
}