【代码随想录】双指针法

总结

通过两个指针在一个 for 循环下完成两个 for 循环的工作。

双指针法将时间复杂度：O (n^2) 的解法优化为 O (n) 的解法。也就是降一个数量级。

移除元素（数组）

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

慢指针指向应该保留的位置，快指针遍历每一个元素。

如果不采用双指针法，要么（1）从前向后遍历数组，如果第 i 个刚好是 val，那么从 i+1 到末尾都需要向前移动一位。时间复杂度 O (n^2)；空间复杂度 O (1)

(2) 额外申请一块长度为 n 的数组，遍历 nums，如果不等于 val 就复制到新的数组。时间复杂度 O (n)；空间复杂度 O (n)

因此，快慢指针实际上就是第（2）种方式的变种，将原始数组作为新的空间，由于慢指针永远不会超过快指针，因此不用担心空间不够。

反转字符串（字符串）

344. 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char [] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O (1) 的额外空间解决这一问题。

左边的指针从左边开始，右边的指针从末尾开始，互相替换。从前向后和从后向前遍历，在一次循环体中获得两边的信息。

替换空格（字符串）

剑指 Offer 05. 替换空格

目前 leetcode 上没有原题，牛客网上有原题。

请实现一个函数，将一个字符串 s 中的每个空格替换成 “%20”。

这道题需要首先统计所有空格信息，然后申请合适大小的空间。

然后快慢指针从后向前遍历。这样可以减少向后移动。

反转字符串里的单词（字符串）

题目：151

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: “ hello world! “
输出: “world! hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good example”
输出: “example good a”
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

这道题首先需要将多余的空格删除：删除首尾空格，然后去除单词中间多余的空格。采用双指针，慢指针指向应该保留的元素，快指针遍历每一个元素。当快指针发现一个字符时，首先添加一个空格（如果 slow 指向 0 也就是第一个单词时，就不添加空格），然后将后面所有不是空格的字符逐渐移动到 slow。

删除多余的空格之后就是先整体反转再局部反转。

反转链表（链表）

题目：206

题意：反转一个单链表。

示例：输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

每次处理相邻两个节点的前后关系，因此需要双指针。在一次循环中，首先保留 cur 的下一个节点信息，然后令 cur 指向 pre。最后更新 pre 和 cur。

删除链表的倒数第 N 个节点（链表）

如果想一次遍历就找到倒数第 N 个节点：从虚拟头节点开始，第一个指针先走 n-1 步指向第 n-1 个节点，接着第二个指针从头开始跟着第一个结点一起走到尾，假设最后一个节点为第 len 个，那么此时第一个指针和第二个指针一起走了 len-n+1 步，就会指向第 len-n+1 也就是倒数第 n 个结点。（倒数第 1 个节点是正数第 len 个，倒数第 2 个节点是正数第 len-1 个，以此类推，倒数第 n 个节点就是正数第 len-n+1 个）

链表相交（链表）

160. 判断两个链表是否相交

方法 1：两个指针分别遍历 A + B 和 B + A，如果相交会提前指向同一个节点，并且就是起点；否则会最终都指向空结点。

方法 2：连接 A+B，判断链表是否有环，以及求环的起点。

环形链表（链表）

142. 找到环的起点

使用快慢指针：链表 A + 链表 B，判断是否存在循环。判断循环链表的方法：使用双指针，快指针每次向后移动两个位置，慢指针每次移动一个位置。如果是循环链表，那么两个指针会在某个节点相遇即节点相同。进入循环条件是快指针后面存在两个节点。如果单链表存在环，则循环不会终止，需要在两个节点相遇时 break。如果不存在环，那么一定能够跳出 while。

判断存在环之后，还需要找到环的起点：1. 使用快慢指针寻找相遇点；2. 当第一次相遇时，令其中一个指针指向头结点，两个指针同速前进，再次相遇点就是环的起点。

原理是假设有三个点：头结点、环的起点、相遇点，相遇点一定在环的起点之后（没到环的起点怎么相遇）。
假设相遇点时 slow 走了 k，那么 fast 一定走了 2k，多走的这一部分是在环中转圈，所以多走的这一部分 k 一定是环的长度的 n 倍。
假设相遇点距离环的起点的距离为 m，那么环的起点点距离头结点的距离为 k-m；即从头结点走 k-m 到达环的起点。
假如从相遇点开始走，再走 k 一定是重新到达相遇点。那么现在两个指针都走 k-m 会到环的起点。

三数之和（哈希表）

15. 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

首先对数组进行排序。

确定 a，从前向后遍历；然后 b 与 c 分别从 a 之后的两端取（双指针），这样由于是排序之后的，如果偏大就令右边左移，否则令左边右移。

这里涉及到筛选，首先是如果 a 大于 0 那么由于 bc 均比 a 大那么不需要再进行判断；另外如果 a 与前面的相同，则说明接下来的判断起点相同，即使找到也是重复的，这里不能与后面的比较，因此同一个三元组内是可以相同的。然后是筛选 bc，同样是判断与相邻的是否相同。

四数之和（哈希表）

18. 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

在三数之和的基础上再加一层循环。