双指针
2026/4/10大约 18 分钟常用算法题双指针
本章题海战术
双指针介绍
面试官提问
同学你好，我们来聊聊算法题吧。你能给我详细讲讲双指针算法吗？包括它的核心思想、适用场景、常见类型以及你实际用过的例子。
候选人回答
💡 好的面试官，没问题。双指针是我在算法题中最常用的技巧之一，它的核心优势是能把暴力解法的 O (n²) 时间复杂度优化到 O (n)，空间复杂度保持 O (1)，非常高效。
核心思想 🎯
简单来说，双指针就是用两个指针同时遍历数据结构（数组 / 链表），通过两个指针的协同移动（相向 / 同向），利用数据的有序性或单调性，在一次遍历中完成原本需要两次遍历的操作，从而大幅提升效率。
适用场景 🚀
当题目中出现以下关键词时，第一时间想到双指针：
- 数组 / 链表的有序性相关问题（求和、去重、查找）
- 数组 / 链表的反转、旋转问题
- 链表的环、中点、倒数节点问题
- 子数组 / 子串的滑动窗口问题
- 两数 / 三数之和类问题
常见类型及经典例题 📊
双指针主要分为 左右指针（首尾指针）和快慢指针（同方向指针） 两大类，滑动窗口是快慢指针的特殊变种。
1 左右指针（相向而行）
- 定义：两个指针分别指向数组的头部
（left=0）和尾部（right=n-1），根据条件向中间移动 - 示意图：
- 经典例题：两数之和 II、反转字符串、三数之和、盛最多水的容器
- Java 代码示例（两数之和 II - 输入有序数组(leetcode 167)）：
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[]{-1, -1};
}2 快慢指针（同向而行）
- 定义：两个指针从同一位置出发，快指针移动速度快于慢指针（通常快指针每次走 2 步，慢指针每次走 1 步）
- 示意图：
- 经典例题：链表中环的检测(leetcode 141)（Floyd 判圈算法）、寻找链表中点(leetcode 876)、删除链表倒数第 N 个节点(leetcode 19)、判断回文链表(leetcode 234)
- Java 代码示例（链表中环的检测(leetcode 141)）：
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // 快慢指针相遇，说明有环
}
return false;
}3 滑动窗口（快慢指针变种）
- 定义：两个指针维护一个动态窗口，右指针扩大窗口，左指针缩小窗口，找到满足条件的最优窗口
- 示意图：
- 经典例题：无重复字符的最长子串(leetcode 3)、长度最小的子数组(leetcode 209)、最长重复子数组(leetcode 718)
左右指针 vs 快慢指针 对比表 📋
| 特性 | 左右指针 | 快慢指针 |
|---|---|---|
| 移动方向 | 相向而行（头↔尾） | 同向而行（都从头部出发） |
| 移动速度 | 相同速度 | 不同速度（快 > 慢） |
| 适用数据结构 | 主要是数组（支持随机访问） | 主要是链表（仅支持顺序访问） |
| 核心解决问题 | 有序数组的求和、查找、反转 | 链表的环、中点、倒数节点 |
面试高频坑点 & 注意事项 ⚠️
- 边界条件：左右指针的终止条件通常是
left < right（避免同一元素被重复使用），一定要根据题目判断 - 重复元素处理：三数之和(leetcode 15)等问题需要跳过重复元素（如
nums[i] == nums[i-1]时跳过），避免结果重复 - 链表空指针：快慢指针中必须先判断
fast != null && fast.next != null，防止空指针异常 - 滑动窗口收缩时机：当窗口满足条件时，要尽可能收缩左指针，找到最优解
高频核心代码 & 技术亮点解析 ✨
1 三数之和(leetcode 15)（中等难度，面试必考）
题目：给你一个整数数组 nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) return res;
Arrays.sort(nums); // 排序预处理 O(nlogn)
for (int i = 0; i < nums.length - 2; i++) {
// 技术亮点1：提前终止优化（最小的数都大于0，不可能有解）
if (nums[i] > 0) break;
// 技术亮点2：第一层去重（跳过相同的i）
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 技术亮点3：第二层去重（跳过相同的left和right）
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}核心技术亮点：
- 将暴力 O (n³) 解法优化到 O (n²)（排序 O (nlogn)+ 双指针 O (n²)）
- 三重去重机制完全避免重复结果，无需额外 Set 存储
- 提前终止优化（当 nums [i]>0 时直接 break），大幅减少不必要的遍历
- 原地排序 + 双指针，空间复杂度仅为 O (logn)（排序的栈空间）
2 删除有序数组中的重复项 II(leetcode 80)（中等难度）
题目：给你一个有序数组 nums，请你原地删除重复出现的元素，使得每个元素最多出现两次，返回删除后数组的新长度。
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
// 技术亮点：慢指针指向"下一个可写入的位置"
int slow = 2;
for (int fast = 2; fast < nums.length; fast++) {
// 技术亮点：只需比较nums[fast]和nums[slow-2]
if (nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}核心技术亮点：
- 通用解法：可扩展到 "每个元素最多出现 k 次"（只需将 2 改为 k）
- 原地修改数组，空间复杂度 O (1)
- 一次遍历完成，时间复杂度 O (n)
- 巧妙的比较逻辑，无需计数变量
3 无重复字符的最长子串(leetcode 3)（中等难度，滑动窗口经典）
题目：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
public int lengthOfLongestSubstring(String s) {
// 技术亮点1：用数组代替HashMap，性能提升10倍以上（字符集有限）
int[] lastIndex = new int[128];
Arrays.fill(lastIndex, -1);
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 技术亮点2：左指针直接跳跃，而非逐个移动
left = Math.max(left, lastIndex[c] + 1);
maxLen = Math.max(maxLen, right - left + 1);
lastIndex[c] = right;
}
return maxLen;
}核心技术亮点：
- 滑动窗口一次遍历，时间复杂度 O (n)
- 用 ASCII 数组代替 HashMap，避免哈希冲突和自动装箱开销
- 左指针直接跳跃到重复字符的下一个位置，而非逐个收缩
- 空间复杂度 O (1)（固定大小的数组）
4 链表中环的入口节点(leetcode 142)（中等难度，Floyd 判圈算法进阶）
题目：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// 第一步：判断是否有环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 第二步：有环，找入口节点
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}核心技术亮点：
- 基于数学证明的 Floyd 判圈算法，正确性有保障
- 无需额外空间，空间复杂度 O (1)
- 两次遍历完成，时间复杂度 O (n)
- 代码简洁优雅，面试中写出会非常加分
双指针技术难点 & 解决方案 🛠️
| 技术难点 | 问题描述 | 解决方案 |
|---|---|---|
| 重复元素导致结果重复 | 三数之和(leetcode 15)、四数之和(leetcode 18)等问题中，重复元素会生成完全相同的结果，不符合题目要求 | 1. 先对数组排序 2. 每层循环跳过与前一个相同的元素 3. 找到解后，继续跳过所有相同的元素 |
| 滑动窗口收缩时机错误 | 不知道什么时候应该收缩左指针，导致结果偏大或偏小 | 1. 明确窗口的"合法条件" 2. 当窗口满足合法条件时，尽可能收缩左指针以找到最优解 3. 收缩时同步更新结果 |
| 链表空指针异常 | 快慢指针中，fast.next.next会在fast到达链表尾部时抛出NPE | 1. 循环条件必须是fast != null && fast.next != null2. 先判断fast，再判断fast.next 3. 提前处理空链表和单节点链表 |
| 多指针协同逻辑混乱 | 四数之和(leetcode 18)等多指针问题，指针移动顺序和条件容易写错 | 1. 固定前n-2个指针 2. 最后两个指针用左右双指针 3. 每层都做去重处理 |
| 原地修改数组边界错误 | 快慢指针中，慢指针的位置错误导致元素被覆盖或遗漏 | 1. 慢指针始终指向下一个可写入的位置 2. 快指针遍历所有元素 3. 初始值根据题目要求设置（如允许k次重复则slow=k） |
//i 层去重
if (i>0 && nums [i]==nums [i-1]) continue;
//left/right 去重
while (left<right && nums [left]==nums [left+1]) left++;
while (窗口满足条件) {
maxLen = Math.max(maxLen, right-left+1);
left++; // 收缩左指针
}
// 正确的循环条件
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
for (int i=0; i<n-3; i++) {
for (int j=i+1; j<n-2; j++) {
int left=j+1, right=n-1;
// 双指针逻辑
}
}
// 允许最多k次重复的通用解法
int slow = k;
for (int fast=k; fast<n; fast++) {
if (nums[fast] != nums[slow-k]) {
nums[slow++] = nums[fast];
}
}总结 ✨
双指针算法的本质是通过指针的协同移动减少不必要的遍历。在面试中，只要看到数组/链表的问题，尤其是涉及到"有序"、"求和"、"子串"、"环"这些关键词，第一时间想到双指针，基本能解决80%以上的中等难度算法题。
真实面试模拟
真实面试模拟
面试官：
好，先来个基础题热热身。谈谈你对“双指针”这个技巧的理解吧。
我：
双指针说白了就是用两个下标变量在数组或链表上移动，把原本可能需要两层循环的暴力枚举，优化成一次遍历。虽然 Java 里没指针，但效果一样。
举个直观的例子：有序数组里找两数之和等于 target。
数组: [2, 7, 11, 15] target=9
↑ ↑
left right初始 left=0, right=3，和=2+15=17 >9 → right 左移；和=2+11=13 >9 → right 再左移；和=2+7=9 命中。一次扫描完事，O(n) 搞定。核心就是利用有序性剪枝，把不可能的组合提前跳过。🧐
面试官：
嗯，那实际做题时，你怎么快速判断一道题能不能用双指针？指针移动有什么套路？
我：
我习惯先问自己三个灵魂问题：
- 数据是否有序或可构造有序？（数组排序、链表天然有序）
- 指针的移动方向由什么决定？
- 能不能把二维搜索降维成一维扫描？
根据移动策略，我把它分成三类，做个表格一目了然：
| 类型 | 移动策略 | 经典题目 | 一句口诀 |
|---|---|---|---|
| 左右夹击 | 左右指针根据条件向内收缩 | 有序数组 Two Sum(leetcode 167)、盛水最多容器(leetcode 11) | 和大了收右边，小了收左边 |
| 快慢指针 | 一快一慢，利用步长差检测结构 | 环形链表(leetcode 141)、寻找链表中点(leetcode 876) | 快针探路，慢针跟步 |
| 滑动窗口 | 右指针扩张、左指针收缩维护窗口 | 最小覆盖子串(leetcode 76)、长度最小子数组(leetcode 209) | 右边吃到满足，左边吐到不满足 |
只要题目能套进这几个框，基本就能用双指针。✨
面试官：
不错，总结得挺清晰。那你现场写一下左右夹击的模板代码吧，注意边界条件。
我：
好的，直接写。
public int[] twoSum(int[] numbers, int target) {
// 基础判空，防止 NPE 和越界
if (numbers == null || numbers.length < 2) return new int[]{-1, -1};
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[]{-1, -1};
}这里我特别留意循环条件用 left < right，如果写成 <=，可能会取到同一个元素，不符合题意。另外，如果题目换成三数之和，还得加上跳过重复元素的逻辑。✍️
面试官：
很好。那滑动窗口的通用模板能写一下吗？很多子串问题都用它。
我：
没问题，滑动窗口更灵活，模板如下：
int left = 0, right = 0;
while (right < s.length()) {
char c = s.charAt(right);
window.add(c); // 扩大窗口
right++;
while (窗口需要收缩) {
char d = s.charAt(left);
window.remove(d); // 缩小窗口
left++;
}
// 在这里更新答案，比如最小长度、是否覆盖等
}核心就是：右指针负责吃进新元素，左指针负责吐掉多余元素。什么时候收缩？通常是窗口内元素满足题目条件时，尝试移动左边界来求最优解。这个模板套过最小覆盖子串、长度最小子数组，屡试不爽。🤓
面试官：
基础扎实。再追问个细节：快慢指针判环时，快指针每次走两步，为什么一定会相遇？走三步行不行？
我：
这个问题能考察对本质的理解。快指针走两步时，相对速度是1，每一轮循环后，快慢指针之间的距离会缩短1，所以一定能在慢指针走完一圈之前相遇，不会跳过。
如果快指针走三步，相对速度就是2。这就有可能在环的长度为偶数时，快指针恰好每次都“跨过”慢指针，导致永不碰头。虽然数学上只要相对速度与环长互质就能相遇，但走两步是最简单、最可靠的做法，也是面试标配答案。这种思考能体现你考虑过极端情况，面试官会比较喜欢。😄
面试官：
最后，如果用一句话向同事介绍双指针，你会怎么说？
我：
双指针就是利用两个游标的相对运动，把暴力枚举的二维搜索优化成一维扫描，关键是想清楚“在什么条件下移动哪个指针”。它就像瑞士军刀 🔪，数组、链表、字符串，到处能用，练熟后刷题效率翻倍。
🔥 核心代码 + 技术亮点
1. 左右夹击（有序数组 Two Sum）(leetcode 167)—— 带重复跳过版
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) return res;
Arrays.sort(nums); // O(nlogn) 排序，为双指针铺路
for (int i = 0; i < nums.length - 2; i++) {
// ✅ 亮点1：跳过外层重复元素，避免结果重复
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// ✅ 亮点2：内层也跳过重复元素，压缩搜索空间
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}技术亮点：
- 排序 + 双指针：将枚举降维，时间复杂度从 O(n³) 降到 O(n²)。
- 双重去重：外层跳过
nums[i]重复，内层跳过left/right重复，避免结果集污染。 - 提前剪枝：实际工程中还可以加
if(nums[i] > 0) break;，因为排序后正数不可能和为 0。
2. 快慢指针（环形链表 II）(leetcode 142)—— 找环入口
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
// ✅ 亮点：先判定是否有环，同时快指针探路
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 第一次相遇
ListNode ptr = head;
while (ptr != slow) { // 等速双指针找入口
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}技术亮点：
- Floyd 判圈算法：快慢指针相遇后，从 head 和相遇点同时同速移动，再次相遇点即为环入口（基于数学推导 a = c + (n-1)(b+c)）。
- 空指针安全：循环条件同时判断
fast != null && fast.next != null，防止空指针异常。 - 时间复杂度 O(n)，空间 O(1)：不用哈希表，内存优势明显。
3. 滑动窗口（最小覆盖子串）(leetcode 76)—— 带哈希表收缩
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
int[] need = new int[128]; // ✅ 亮点：用数组代替 HashMap，更快
for (char c : t.toCharArray()) need[c]++;
int left = 0, right = 0, count = t.length(), start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
if (need[c] > 0) count--; // 命中有效字符
need[c]--; // 窗口内消耗一个
right++;
while (count == 0) { // 窗口已覆盖所有字符
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d = s.charAt(left);
need[d]++; // 吐出字符
if (need[d] > 0) count++; // 如果缺口重新出现
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}技术亮点：
int[128]代替 HashMap：ASCII 字符集下，数组常数时间更新，效率极高。count计数技巧：用count记录仍需匹配的字符个数，避免每次检查整个哈希表。- 惰性收缩：当
count == 0时才收缩左边界，确保正确性下追求最小窗口。
🧩 技术难点 & 解决方案总结
| 技术难点 | 常见现象 | 解决方案 |
|---|---|---|
| 指针移动条件不清晰 | 写不出 if-else，死循环或遗漏 | 画图+口诀：“和大了收右，小了收左”；滑动窗口：“右边吃到满足，左边吐到不满足” |
| 重复元素导致结果冗余 | 三数之和、四数之和出现重复解 | 排序后，外层 if(i>0 && nums[i]==nums[i-1]) continue; 内层 找到解后跳过相同值 |
| 快慢指针为什么一定相遇 | 对 Floyd 算法半信半疑 | 理解相对速度：快指针走2步，慢指针走1步，每次循环距离缩小1，必然相遇；走三步行不通（偶数环可能跳过） |
| 滑动窗口何时收缩 | 不知道在 while 里写收缩条件，或收缩时机错误 | 窗口满足题目条件后立即收缩，在收缩过程中更新最优解；条件通常是 count==0 或 sum>=target |
| 链表空指针/越界 | 忘记判断 fast.next != null | 模板化：快指针循环条件固定 while(fast != null && fast.next != null)，养成肌肉记忆 |
| 窗口用 HashMap 性能瓶颈 | 字符串很长时频繁哈希计算 | 改用 int[128] 或 int[26] 数组，键直接索引 ASCII，更新 O(1) 且常数极小 |
| 双指针边界设定 | 左右指针初始值、终止条件错误 | 记住：找两个不同元素用 left < right；滑动窗口右边界终止在 right < len |
把这些代码和难点吃透，双指针类题目基本可以见招拆招。后面你可以拿 盛水最多的容器(leetcode 11)、删除排序数组重复项(leetcode 80)、无重复字符的最长子串(leetcode 3) 这些经典题练手，相信你很快就能形成条件反射 🚀