代码随想录—双指针 | Aryue的个人博客

type

status

date

slug

summary

📝基础理论

双指针不是某种具体的数据结构，而是一种解题思想。在多个模块的问题中都会用到这种思想，因此需要单独列出一篇文章来进行总结。

双指针入门题目，用两个指针将两个for循环的工作变成一个for循环的工作。

在字符串：这道题目，使用库函数一行代码搞定 (opens new window)中讲解了反转字符串，注意这里强调要原地反转，要不然就失去了题目的意义。

使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。时间复杂度是O(n)。

在替换空格 (opens new window)中介绍使用双指针填充字符串的方法，如果想把这道题目做到极致，就不要只用额外的辅助空间了！

思路就是首先扩充数组到每个空格替换成"%20"之后的大小。然后双指针从后向前替换空格。

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么在字符串：花式反转还不够！ (opens new window)中，我们使用双指针法，用O(n)的时间复杂度完成字符串删除类的操作，因为题目要删除冗余空格。

在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。

主要还是大家用erase用的比较随意，一定要注意for循环下用erase的情况，一般可以用双指针写效率更高！

链表中的一些问题，实际上是数学问题。常见的一些思路，你在遇到这个问题之前，基本上是想不到的。而双指针只是辅助思路实现的手段，例如快慢指针。

对于求 n 个数之和等于 0 或者目标值的问题，乍一看，算法的时间复杂度貌似是 n 的几次方。但是通过使用双指针法，可以将时间复杂度降低一个数量级。熟悉这种思路后，这类题目就会变得容易。

笔者的经验是，遇到一个题目，先看暴力解法的时间复杂度是多少，这个非常容易判断。那么正确解法的时间复杂度一般会低一个数量级或者低一个 logn 的数量级。通过逆向推理的方式思考即可。

在双指针板块中，所有的题目之前都已经做过了。这恰好适合在7月重新开始刷题时，对之前的题目进行全面复习。

致谢：

💡

Written by Gao Yue,editted by Notion AI.