【爱吃面筋】ai面经八股刷题系列——双指针专题
最新回答
白色季节
2026-07-31 14:29:08
双指针是一种常用的算法技巧，主要用于优化数组、字符串和链表等数据结构的操作。其核心思想是通过两个指针在数据结构上移动，以降低时间或空间复杂度。以下是双指针的详细解析：
双指针的核心作用- 降低时空复杂度：适用于数组和字符串（非链表），通过双指针减少不必要的操作。
- 链表操作：用于反转链表、检测环、判断链表相交等。
- 方向：
同向指针（快慢指针）：如链表反转、检测环。
反向指针（相向指针）：如字符串反转、两数之和。
- 控制点：
指针是否先移动（如快指针先走n步）。
是否需要排序或结合其他操作（如数组扩容后逆向填充）。
- 纯技巧型：如链表反转（手熟）。
- 带技巧的题目：
检测链表环及环长度（快慢指针）。
链表相交（计算长度差，快指针先走差值步）。
- 降低复杂度：
数组/字符串的删除或替换（快指针覆盖慢指针）。
N数之和（排序后双指针逼近目标值）。
快慢指针覆盖删除：
题目：
27. 移除元素方法：快指针遍历，慢指针记录有效位置，快指针遇到非val值时覆盖慢指针。示例：nums = [3,2,2,3], val = 3 → 慢指针最终指向[2,2]，返回长度2。相向指针反转字符串：
题目：
344. 反转字符串方法：双指针从两端向中间交换字符。示例：s = ['h','e','l','l','o'] → 反转后为['o','l','l','e','h']。逆向填充替换字符：
题目：替换数字为"number"（如"a1b2" → "anumberbnumber"）。方法：从右向左遍历，动态扩容数组并填充，避免覆盖问题。
去除多余空格：
题目：
151. 翻转字符串里的单词步骤：快慢指针去除多余空格。
反转整个字符串。
反转每个单词。
反转链表：
题目：
206. 反转链表方法：双指针（prev和curr）逐个反转节点指向。示例：1→2→3 → 3→2→1。删除倒数第N个节点：
题目：
19. 删除链表的倒数第N个节点技巧：快指针先走N步，快慢指针同步移动，快指针到末尾时慢指针指向待删节点的前驱。链表相交：
题目：
160. 链表相交方法：计算两链表长度差，快指针先走差值步，再同步移动直到相遇。检测环并找入口：
题目：
142. 环形链表II步骤：快慢指针相遇证明有环。
慢指针回到起点，快慢指针同步移动，再次相遇点为环入口。
- 三数之和：
题目：
15. 三数之和方法：排序后固定一个数，双指针逼近剩余两数之和为-fixed。注意：跳过重复值避免重复解。
双指针的核心在于通过控制指针的移动方向和速度，减少冗余操作。其应用场景包括：
- 数组/字符串：原地修改、去重、反转、替换。
- 链表：反转、环检测、相交判断、定位节点。
- 复杂度优化：如N数之和通过排序和双指针将O(n3)降至O(n2)。
掌握双指针需理解数据结构的特性（如数组的连续性、链表的非连续性），并通过练习熟悉不同场景下的指针控制策略。
热门标签
