双指针技巧

相关源文件

• README.md

目的与范围

双指针技巧是一种基本的算法策略，它使用两个指针来更有效地解决问题。本文档解释了双指针技巧的核心概念、常见模式以及在不同数据结构中的应用。与可能使用嵌套循环（O(n²) 时间复杂度）的朴素方法不同，双指针技巧通过策略性地操作指针位置，通常能实现 O(n) 的时间复杂度。

本页面专门介绍算法技巧本身及其变体。有关链表等数据结构中的具体实现，请参见链表；或有关“三数之和”等特定问题类型中的应用，请参见哈希表。

什么是双指针技巧？

双指针技巧涉及在数据结构中使用两个参照点（指针），以比使用单个指针或嵌套迭代更有效的方式解决问题。

来源：README.md:152-166

双指针技巧的关键模式

1. 相向（左右）模式

这种模式将指针初始化在数据结构（通常是数组）的两端，然后让它们相向移动。

常见应用

• 两数之和（在有序数组中）
• 盛最多水的容器
• 验证回文
• 反转数组/字符串

来源：README.md:156-159, README.md:164-165

2. 快慢指针模式

在这种模式中，一个指针移动速度比另一个快，常用于链表和环检测问题。

常见应用

• 查找链表中的环
• 查找链表的中间元素
• 查找倒数第k个元素

来源：README.md:160-163

3. 同向模式

两个指针同向移动，但保持特定的关系。

常见应用

• 滑动窗口问题
• 查找具有特定属性的子数组
• 删除重复项
• 将零移动到末尾

来源：README.md:156-157

在各种数据结构中的应用

数据结构	常见问题	使用的模式
数组	移除元素、有序数组的平方、最小尺寸子数组和	左右（相向）、同向
字符串	反转字符串、字符串旋转、替换数字	左右（相向）、同向
链表	检测环、查找中间元素、删除倒数第N个节点	快慢指针
多个数组	合并有序数组、数组交集	同向

来源：README.md:156-165

特定问题的应用

1. 数组问题

在数组问题中，双指针可以通过消除嵌套循环来显著降低时间复杂度。例如，在“移除元素”问题中，我们使用快慢指针技巧来高效地移除元素，而无需额外空间。

来源：README.md:106-107, README.md:164-165

2. 字符串问题

双指针技巧在字符串操作问题中特别有效，例如反转字符串、验证回文或执行原地修改。

该仓库中的示例包括

• 反转字符串 (问题 344)
• 字符串旋转 (Kamacoder 问题 0055)
• 字符串单词反转 (问题 151)

来源：README.md:143-147

3. 链表问题

在链表中，快慢指针模式特别有用。例如，在环检测中，如果存在环，快指针最终会追上慢指针。

来源：README.md:160-163

实现考量

实现双指针技巧时

1. 初始化：根据模式正确设置初始位置
2. 移动逻辑：定义指针何时以及如何移动的清晰规则
3. 终止条件：明确何时停止移动指针
4. 边界情况：处理空结构、单个元素或其他特殊情况
5. 指针关系：维护指针之间所需的间距或关系

时间与空间复杂度

双指针技巧的一个关键优势是其效率

• 时间复杂度：通常为 O(n)，因为我们只遍历数据结构一次
• 空间复杂度：通常为 O(1)，因为无论输入大小如何，我们只使用两个指针

这明显优于使用嵌套循环的朴素方法中常见的 O(n²) 时间复杂度。

何时使用双指针技巧

当遇到以下情况时，可以考虑使用双指针技巧：

1. 需要查找具有特定属性的对或子数组
2. 正在处理有序数组或链表
3. 需要检测环
4. 希望执行原地操作且无需额外空间
5. 面对朴素解决方案需要嵌套循环的问题

总结

双指针技巧是一种通用的问题解决方法，可以显著提高各种数据结构中算法的效率。通过理解不同的模式及其应用，您可以运用此技巧以最佳时间和空间复杂度解决各种算法问题。

来源：README.md:152-166