【超详细】双指针算法 核心知识点全解析（含多场景代码实现 + 生活应用）

一、前言

双指针（Two Pointers）是编程中最经典、最高效的算法技巧之一，其核心是通过两个「指针（索引 / 引用）」遍历数据结构，根据条件动态调整指针位置，从而将嵌套循环的 O(n2) 时间复杂度优化为线性的 O(n)。与二分查找（聚焦「折半缩小范围」）不同，双指针更侧重「线性遍历 + 指针协作」，广泛应用于数组、链表、字符串等线性数据结构的问题求解。本文将从核心概念、分类及原理、多场景代码实现、面试题实战、生活场景应用等维度，帮你彻底掌握双指针的精髓，解决新手最头疼的「指针移动逻辑」「边界处理」等问题。

二、双指针核心概念

2.1 定义

双指针是指在遍历数据结构（数组、链表、字符串等）时，使用两个「指针」（本质是数组索引 / 链表节点引用）指向不同位置，通过指针的移动规则（同向 / 反向、快慢）协作完成任务，核心目标是「减少遍历次数，优化时间复杂度」。

2.2 核心前提

2.3 双指针的核心分类（按移动方向）

2.4 核心思想

双指针的本质是「用两个指针替代嵌套循环」，通过一次遍历完成原本需要两层循环的任务：

三、双指针执行流程（可视化）

3.1 左右指针：有序数组两数之和

以升序数组 [1,3,5,7,9,11] 找和为 10 的两个数为例：

初始：left=0（值1），right=5（值11）→ 和=12 > 10 → right左移（right=4，值9） 第1轮：left=0（1）+ right=4（9）=10 → 找到，返回[0,4]

若找和为8的两个数： 初始：left=0（1）+ right=5（11）=12>8 → right=4（9） 第1轮：1+9=10>8 → right=3（7） 第2轮：1+7=8 → 找到，返回[0,3]

3.2 快慢指针：数组去重

以数组 [1,1,2,2,3,4,4,5] 去重为例：

初始：slow=0（慢指针，记录唯一元素位置），fast=1（快指针，遍历数组） 第1轮：nums[fast]=1 == nums[slow]=1 → fast右移（fast=2） 第2轮：nums[fast]=2 != nums[slow]=1 → slow右移（slow=1），nums[slow]=2，fast右移（fast=3） 第3轮：nums[fast]=2 == nums[slow]=2 → fast右移（fast=4） 第4轮：nums[fast]=3 != nums[slow]=2 → slow右移（slow=2），nums[slow]=3，fast右移（fast=5） … 最终slow=4，去重后数组为[1,2,3,4,5]

四、多场景代码实现（Java 版）

4.1 基础版 1：左右指针（有序数组两数之和）

场景：给定升序数组，找两个数之和等于目标值，返回索引（要求时间 O (n)，空间 O (1)）。

/**
* 左右指针：有序数组两数之和
*/
public class TwoSumWithTwoPointers {
public static int[] twoSum(int[] nums, int target) {
// 1. 边界处理
if (nums == null || nums.length < 2) {
return new int[]{-1, -1};
}

// 2. 初始化左右指针（两端向中间）
int left = 0;
int right = nums.length – 1;

while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 找到目标，返回索引
return new int[]{left, right};
} else if (sum > target) {
// 和太大，右指针左移（减小和）
right–;
} else {
// 和太小，左指针右移（增大和）
left++;
}
}

// 未找到
return new int[]{-1, -1};
}

// 测试
public static void main(String[] args) {
int[] nums = {1,3,5,7,9,11};
int[] result1 = twoSum(nums, 10);
System.out.println("和为10的索引：" + result1[0] + "," + result1[1]); // 0,4

int[] result2 = twoSum(nums, 8);
System.out.println("和为8的索引：" + result2[0] + "," + result2[1]); // 0,3

int[] result3 = twoSum(nums, 20);
System.out.println("和为20的索引：" + result3[0] + "," + result3[1]); // -1,-1
}
}

4.2 基础版 2：快慢指针（数组去重）

场景：给有序数组原地去重，返回去重后数组长度（要求空间 O (1)）。

/**
* 快慢指针：有序数组去重（原地修改）
*/
public class RemoveDuplicates {
public static int removeDuplicates(int[] nums) {
// 1. 边界处理
if (nums == null || nums.length == 0) {
return 0;
}

// 2. 初始化快慢指针（慢指针记录唯一元素位置，快指针遍历）
int slow = 0; // 慢指针：指向最后一个唯一元素
for (int fast = 1; fast < nums.length; fast++) {
// 3. 快指针找到不同元素，慢指针右移并赋值
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
// 相同则仅快指针右移（跳过重复元素）
}

// 4. 慢指针+1为去重后数组长度
return slow + 1;
}

// 测试
public static void main(String[] args) {
int[] nums = {1,1,2,2,3,4,4,5};
int newLength = removeDuplicates(nums);
System.out.println("去重后长度：" + newLength); // 输出5
System.out.print("去重后数组：");
for (int i = 0; i < newLength; i++) {
System.out.print(nums[i] + " "); // 输出1 2 3 4 5
}
}
}

4.3 基础版 3：快慢指针（链表判环）

场景：判断单链表是否有环（如尾节点指向中间节点），经典「龟兔赛跑」算法。

/**
* 链表节点定义
*/
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}

/**
* 快慢指针：判断链表是否有环
*/
public class LinkedListCycle {
public static boolean hasCycle(ListNode head) {
// 1. 边界处理
if (head == null || head.next == null) {
return false;
}

// 2. 初始化快慢指针（慢指针走1步，快指针走2步）
ListNode slow = head; // 龟
ListNode fast = head.next; // 兔

while (slow != fast) {
// 快指针走到头，无环
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next; // 慢指针走1步
fast = fast.next.next; // 快指针走2步
}

// 快慢指针相遇，有环
return true;
}

// 测试
public static void main(String[] args) {
// 构造有环链表：1→2→3→2
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
node3.next = node2; // 环
System.out.println("链表是否有环：" + hasCycle(node1)); // 输出true

// 构造无环链表：1→2→3→null
ListNode node4 = new ListNode(1);
ListNode node5 = new ListNode(2);
ListNode node6 = new ListNode(3);
node4.next = node5;
node5.next = node6;
System.out.println("链表是否有环：" + hasCycle(node4)); // 输出false
}
}

4.4 进阶版：滑动窗口（最长无重复子串）

场景：找字符串中最长无重复字符的子串长度（同向双指针的典型应用）。

import java.util.HashSet;
import java.util.Set;

/**
* 同向指针（滑动窗口）：最长无重复子串
*/
public class LengthOfLongestSubstring {
public static int lengthOfLongestSubstring(String s) {
// 1. 边界处理
if (s == null || s.length() == 0) {
return 0;
}

// 2. 初始化同向指针（滑动窗口左右边界）+ 存储窗口内字符
Set<Character> charSet = new HashSet<>();
int left = 0; // 窗口左边界
int maxLen = 0; // 最长长度

// 3. 右指针遍历字符串（窗口右边界）
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 4. 有重复字符，左指针右移（缩小窗口）直到无重复
while (charSet.contains(c)) {
charSet.remove(s.charAt(left));
left++;
}
// 5. 添加当前字符到窗口
charSet.add(c);
// 6. 更新最长长度
maxLen = Math.max(maxLen, right – left + 1);
}

return maxLen;
}

// 测试
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 输出3（"abc"）
System.out.println(lengthOfLongestSubstring("bbbbb")); // 输出1（"b"）
System.out.println(lengthOfLongestSubstring("pwwkew")); // 输出3（"wke"）
}
}

五、双指针的优缺点 & 适用场景

适用场景

六、经典面试题实战（附思路 + 代码）

6.1 题目 1：反转字符串（LeetCode 344）

题目描述：原地反转字符数组（如 ['h','e','l','l','o'] → ['o','l','l','e','h']）。思路：左右指针从两端向中间移动，交换指针指向的字符，直到指针相遇。

/**
* 左右指针：反转字符串（原地修改）
*/
public class ReverseString {
public static void reverseString(char[] s) {
if (s == null || s.length <= 1) {
return;
}

int left = 0;
int right = s.length – 1;
while (left < right) {
// 交换左右指针字符
char temp = s[left];
s[left] = s[right];
s[right] = temp;
// 指针移动
left++;
right–;
}
}

public static void main(String[] args) {
char[] s = {'h','e','l','l','o'};
reverseString(s);
System.out.println(s); // 输出olleh
}
}

6.2 题目 2：删除链表的倒数第 N 个节点（LeetCode 19）

题目描述：删除单链表的倒数第 n 个节点，返回头节点。思路：快慢指针，快指针先走 n 步，然后快慢指针同步走，快指针到尾时，慢指针指向倒数第 n 个节点的前一个节点。

/**
* 快慢指针：删除链表倒数第N个节点
*/
public class RemoveNthFromEnd {
public static ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头节点（处理删除头节点的情况）
ListNode dummy = new ListNode(0);
dummy.next = head;

// 初始化快慢指针
ListNode fast = dummy;
ListNode slow = dummy;

// 快指针先走n步
for (int i = 0; i < n; i++) {
fast = fast.next;
}

// 快慢指针同步走，直到快指针到尾
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}

// 删除慢指针的下一个节点（倒数第n个）
slow.next = slow.next.next;

return dummy.next;
}

// 辅助方法：遍历链表
public static void traverse(ListNode head) {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " -> ");
cur = cur.next;
}
System.out.println("null");
}

public static void main(String[] args) {
// 构造链表：1→2→3→4→5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// 删除倒数第2个节点（4）
ListNode newHead = removeNthFromEnd(head, 2);
traverse(newHead); // 输出1 -> 2 -> 3 -> 5 -> null
}
}

6.3 题目 3：三数之和（LeetCode 15）

题目描述：给数组找所有不重复的三元组 [a,b,c]，满足 a+b+c=0。思路：排序 + 左右指针，固定第一个数，用左右指针找另外两个数，时间 O (n²)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 排序+左右指针：三数之和
*/
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 1. 边界处理
if (nums == null || nums.length < 3) {
return result;
}

// 2. 排序（去重+满足左右指针条件）
Arrays.sort(nums);

// 3. 固定第一个数，左右指针找另外两个数
for (int i = 0; i < nums.length; i++) {
// 去重：第一个数重复则跳过
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}

int target = -nums[i]; // b + c = -a
int left = i + 1;
int right = nums.length – 1;

while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 找到三元组，加入结果
result.add(Arrays.asList(nums[i], nums[left], nums[right]));

// 去重：左指针重复
while (left < right && nums[left] == nums[left+1]) {
left++;
}
// 去重：右指针重复
while (left < right && nums[right] == nums[right-1]) {
right–;
}

// 指针移动
left++;
right–;
} else if (sum < target) {
left++;
} else {
right–;
}
}
}

return result;
}

public static void main(String[] args) {
int[] nums = {-1,0,1,2,-1,-4};
List<List<Integer>> result = threeSum(nums);
System.out.println("三数之和为0的三元组：");
for (List<Integer> list : result) {
System.out.println(list); // 输出[-1,-1,2]、[-1,0,1]
}
}
}

七、生活中的双指针实战（3 个场景 + 完整代码）

双指针并非只适用于算法题，生活中很多场景能通过双指针思想提升效率，以下是 3 个典型场景及 Java 实现。

7.1 场景 1：超市找两件商品总价等于预算

7.1.1 场景描述

你有固定预算（如 100 元），超市货架上的商品价格按升序排列（如 [20,30,40,50,60,70]），用双指针快速找两件商品总价刚好等于预算的组合，替代逐个试算。

7.1.2 解决思路

• 左右指针分别指向价格数组两端；
• 计算两数之和：和等于预算则找到；和大于预算则右指针左移；和小于预算则左指针右移；
• 遍历至指针相遇，未找到则返回无。

7.1.3 Java 代码实现

/**
* 生活场景1：双指针找两件商品总价等于预算
*/
public class FindTwoGoodsByBudget {
/**
* 查找总价等于预算的两件商品价格
* @param prices 升序的商品价格数组
* @param budget 预算
* @return 价格组合，未找到返回空数组
*/
public static int[] findTwoGoods(int[] prices, int budget) {
if (prices == null || prices.length < 2) {
return new int[0];
}

int left = 0;
int right = prices.length – 1;

while (left < right) {
int sum = prices[left] + prices[right];
if (sum == budget) {
return new int[]{prices[left], prices[right]};
} else if (sum > budget) {
// 总价超预算，选更便宜的（右指针左移）
right–;
} else {
// 总价不足，选更贵的（左指针右移）
left++;
}
}

// 未找到
return new int[0];
}

public static void main(String[] args) {
int[] prices = {20,30,40,50,60,70};
int budget1 = 100;
int[] result1 = findTwoGoods(prices, budget1);
if (result1.length == 2) {
System.out.println("预算" + budget1 + "元的组合：" + result1[0] + "+" + result1[1]); // 30+70 或 40+60
} else {
System.out.println("预算" + budget1 + "元无匹配组合");
}

int budget2 = 150;
int[] result2 = findTwoGoods(prices, budget2);
if (result2.length == 2) {
System.out.println("预算" + budget2 + "元的组合：" + result2[0] + "+" + result2[1]);
} else {
System.out.println("预算" + budget2 + "元无匹配组合"); // 输出无
}
}
}

7.2 场景 2：排队找最长连续无重复人员的队伍

7.2.1 场景描述

超市结账队伍中，人员按编号排列（如 [1,2,3,2,4,5,5,6]），用双指针（滑动窗口）找最长连续无重复编号的子队伍，方便收银员快速引导至该队伍。

7.2.2 解决思路

• 同向指针（滑动窗口）：left 为窗口左边界，right 为窗口右边界；
• 用集合存储窗口内的人员编号，遇到重复则移动左边界直到无重复；
• 记录窗口的最大长度，即为最长无重复队伍长度。

7.2.3 Java 代码实现

import java.util.HashSet;
import java.util.Set;

/**
* 生活场景2：双指针找最长连续无重复人员的队伍
*/
public class FindLongestUniqueQueue {
/**
* 查找最长连续无重复人员编号的队伍长度
* @param personIds 人员编号数组
* @return 最长长度
*/
public static int findLongestUniqueQueue(int[] personIds) {
if (personIds == null || personIds.length == 0) {
return 0;
}

Set<Integer> idSet = new HashSet<>();
int left = 0;
int maxLen = 0;

for (int right = 0; right < personIds.length; right++) {
int curId = personIds[right];
// 有重复，移动左边界
while (idSet.contains(curId)) {
idSet.remove(personIds[left]);
left++;
}
idSet.add(curId);
// 更新最长长度
maxLen = Math.max(maxLen, right – left + 1);
}

return maxLen;
}

public static void main(String[] args) {
int[] personIds = {1,2,3,2,4,5,5,6};
int maxLen = findLongestUniqueQueue(personIds);
System.out.println("最长连续无重复人员的队伍长度：" + maxLen); // 输出4（[2,4,5,6]）

int[] personIds2 = {1,1,1,1};
int maxLen2 = findLongestUniqueQueue(personIds2);
System.out.println("最长连续无重复人员的队伍长度：" + maxLen2); // 输出1
}
}

7.3 场景 3：快递站找循环堆放的包裹链

7.3.1 场景描述

快递站的包裹按「链表」方式堆放（每个包裹贴有下一个包裹的编号），可能出现循环（如包裹 1→2→3→2），用快慢指针快速判断是否有循环，避免分拣时无限遍历。

7.3.2 解决思路

• 快慢指针：慢指针每次找下一个包裹，快指针每次找下下个包裹；
• 若快慢指针指向同一个包裹，说明有循环；若快指针找到末尾（无下一个包裹），则无循环。

7.3.3 Java 代码实现

import java.util.HashMap;
import java.util.Map;

/**
* 生活场景3：双指针判断包裹链是否有循环
*/
public class CheckPackageCycle {
// 模拟包裹映射：key=当前包裹编号，value=下一个包裹编号（null表示无）
private static Map<Integer, Integer> packageMap = new HashMap<>();

/**
* 判断包裹链是否有循环
* @param startId 起始包裹编号
* @return 是否有循环
*/
public static boolean hasPackageCycle(int startId) {
// 无起始包裹
if (!packageMap.containsKey(startId)) {
return false;
}

// 快慢指针（包裹编号）
int slow = startId;
int fast = startId;

while (true) {
// 慢指针走1步
slow = packageMap.get(slow);
// 快指针走1步
fast = packageMap.get(fast);
// 快指针无下一个包裹，无循环
if (fast == null) {
return false;
}
// 快指针再走1步
fast = packageMap.get(fast);
// 快指针走到头，无循环
if (fast == null) {
return false;
}
// 快慢指针相遇，有循环
if (slow == fast) {
return true;
}
}
}

public static void main(String[] args) {
// 构造有循环的包裹链：1→2→3→2
packageMap.put(1, 2);
packageMap.put(2, 3);
packageMap.put(3, 2);
System.out.println("包裹链是否有循环：" + hasPackageCycle(1)); // 输出true

// 清空并构造无循环的包裹链：4→5→6→null
packageMap.clear();
packageMap.put(4, 5);
packageMap.put(5, 6);
packageMap.put(6, null);
System.out.println("包裹链是否有循环：" + hasPackageCycle(4)); // 输出false
}
}

八、总结

核心要点回顾

学习建议

文末小结：双指针的核心不是「写代码」，而是「指针协作的思想」—— 用两个指针替代嵌套循环，通过一次遍历完成任务。无论是算法题还是日常生活，只要抓住「线性结构」和「指针移动规则」两个核心，就能用双指针解决问题，大幅提升效率。建议多写、多测、多模拟，让双指针成为你的「算法优化利器」。