双指针总结

标签: 双指针, 总结

本总结主要是对 LeetCode 官方的 LeetBook 进行笔记的整理和练习题的汇总

题型

1. 数组中的题型大致分为：一头一尾 & 两个头
   • 一头一尾：在序列的首尾各放一个指针，经过一定条件的判断，将其中一个指针向序列中部靠拢，直到找到有效答案。
   • 两个头：在序列的首部放两个指针，在一定的条件下，两个指针以不同的步长向后移动，直到找到有效答案。
2. 当然，链表中也可以使用双指针，常见的是利用快慢指针来解题。

1. 一头一尾

1. 初始化一头一尾的指针，然后对序列进行操作（如交换元素等），再向序列的中间靠拢。
2. 图源来自 LeetCode 官方：

相关题目

No	Problem	Difficulty	Link	Solution	Comment
1	两数之和	简单	题目	题解	这道题不用双指针，但是和「167 两数之和 II」相关。
131	分割回文串	中等	题目	题解	双指针在回文串中的应用还是比较经典的
167	两数之和 II	简单	题目	题解	读懂题意再使用一头一尾双指针就可以解出来。也可以使用哈希表的方法。
344	反转字符串	简单	题目	题解	看懂上面的动图就会做的一道题
541	反转字符串 II	简单	题目	题解	和 344 反转字符串 相差无几
561	数组拆分 I	简单	题目	题解	这个双指针不太明显？🥲

2. 两个头（非链表）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

1. 思路 1: 初始化一个新的数组，将原始数组中，任何不等于 val 的元素都填入新数组中。
2. 思路 2: 要求 原地移除
   1. 初始化一个快指针 fast 和一个慢指针 slow；
   2. fast：每次都向前移动一步；
   3. slow：只有当 fast 不指向 val 时才向前移动。
3. 参考代码：

    class Solution:
       def removeElement(self, nums: List[int], val: int) -> int:
           slow = 0
           for fast in range(len(nums)):
               if nums[fast] != val:
                   nums[slow] = nums[fast]
                   slow += 1
           return slow
   

相关题目

No	Problem	Difficulty	Link	Solution	Comment
27	移除元素	简单	题目	题解	快慢指针在数组里的使用，看懂上面动图就可以做的题。
209	长度最小的子数组	中等	题目	题解	既可以用双指针的滑动窗口，又可以用二分法，是一道很好的练习题
485	最大连续 1 的个数	简单	题目	题解	与 27 移除元素 相差无几

3. 两个头 （链表）

1. 在链表题中，双指针是很常用的技巧。通常，这两个指针都是从链表的头部出发。至于指针在什么时候移动，是否有预处理，以什么速度移动，则需要根据题目的特点来分析。

2. 链表中的双指针可以有不同的走法，如：
   1. 一个指针每次移动一步，另一个指针每次移动两步。
   2. 一个指针先移动 n 步，然后两个指针同时以每次一步的速度移动。
3. 针对这两种的走法有这些题目：
   1. 不同速度的双指针：判断链表是否有环
   2. 相同速度不同起点的双指针：倒数第N个节点、删除链表的倒数第N个结点 、找到相交链表的交点
   3. 以及两种方式结合的： 找到环形链表的入口节点

相关题目

No	Problem	Difficulty	Link	Solution	Comment
141	环形链表	简单	题目	题解	快慢指针在链表的经典应用
142	环形链表 II	中等	题目	题解	快慢指针在链表的经典应用，比 141 环形链表 更进阶一丢丢～
160	相交链表	简单	题目	题解	即可以用栈来实现，也可以用双指针来实现。双指针是如何对算法的空间复杂度进行优化的，这道题是个很好的例子。
剑指 Offer 22	链表中倒数第k个节点	简单	题目	题解	速度相同的快慢指针在链表的经典应用
19	删除链表的倒数第 N 个结点	中等	题目	题解	速度相同的快慢指针在链表的经典应用，该题解是基于 链表中倒数第k个节点 的解法进阶而来，需要注意链表的一些边界处理～