【代码随想录】双指针法
总结
通过两个指针在一个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 相等？找出所有满足条件且不重复的四元组。
在三数之和的基础上再加一层循环。