题目来源于：https://books.halfrost.com/leetcode/ChapterTwo/Two_Pointers/

15. 三数之和 思路

题目链接：https://leetcode.cn/problems/3sum/description/

思路：排序，加双指针，两个循环

注意点：

  1. 边界条件，如果数组中数量少于3个，直接返回
  2. 如果排序后第一个数字大于0，直接返回
  3. 重复元素跳过，防止重复解

关联目标：双指针刷题 2/76

16. 最接近的三数之和

类似题目：https://leetcode.cn/problems/3sum-closest/solutions/301382/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/

总体思路和上面的题目类似，a + b + c >= target的时候；移动右指针，a + b +c <= target的时候，移动左指针。

关联目标：双指针刷题 3/76

18. 四数之和

题目链接：https://leetcode.cn/problems/4sum/

思路：仍然是排序加双指针，但难点在于不能有重复解，需要在各层循环中排除重复元素。

关联目标：双指针刷题 4/76

19. 删除链表的倒数第 N 个结点

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

  1. 先让第一个指针向后遍历N个结点，然后第一个指针和第二个指针同时向后跑，直到第一个指针跑到末尾。
  2. 但需要删除第N个结点，所以需要让第二个指针指向被删除结点的前置结点，所以前文说的先遍历N个结点还是N+1结点， 可以找一个例子试一下。
  3. 由于需要返回链表，记得保存头节点

关联目标：双指针刷题 5/76

26. 删除有序数组中的重复项

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

如果L和R不一样，则好兄弟一起走

0 1 2 3 4 
L R
  L R

如果L和R一样，则R先走一步，直到L和R不一样，然后需要把R复制到L的右边，然后好兄弟再一起走

0 0 1 1
L R
L   R
0 1 1 1
  L   R

关联目标：双指针刷题 6/76

27. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/

和26基本一样，用一个指针一直向后移动，直到找到一个不等于target的，然后复制到另外一个指针，复制完再一起移动
target = 0

0 0 1 
L
R

0 0 1
L
  R

0 0 1
L
    R

将1复制到L所在的位置
1 0 1
    L
    R

关联目标：双指针刷题 7/76

28. 找出字符串中第一个匹配项的下标

题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

这题不就是找子串么，KMP算法，但用双指针的思想去想一想，感觉又能多理解一点KMP算法。

最一开始想到是这样一种朴素的双指针方法


haystack: aaaaab
needle:   aaab

当发现index=3时，发现两者不匹配，移动字符串如下

aaaaab
    aaab

但这样移动之后就会发现，将找不到有效解，但实际上这个例子是有解的，说明我这种移动方式是有问题的。
再来一种保守的移动方式，当发现不匹配之后，haystack的指针往后移动一位。这样的移动方式又过于保守，所以效率不高。

aaaaab
 aaab

kmp算法就是解决了以下问题：当needle单词的第n个字母不匹配时，应该向后面移动多少位。

needle: ABCDABD
next    0000120

借用阮一峰老师的文章解释next数组的生成原理, https://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

－　"A"的前缀和后缀都为空集，共有元素的长度为0；
－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－　“ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1；
－　“ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2；
－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

怎么用呢，很简单

haystack: 前面省略ABCDABE后面省略
needle:          ABCDABD

这种情况下，匹配到needle的ABCDAB，先用上文提到的暴力法直接移动成下面这个样子

haystack: 前面省略ABCDABE后面省略
needle:                ABCDABD

对应的next数组中的值为2，再往前移动两位

haystack: 前面省略ABCDABE后面省略
needle:              ABCDABD

好了，我对于KMP的算法理解到这里，至于next数组的计算，看这篇题解：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

关联目标：双指针刷题 8/76

31. 下一个排列

题目链接：https://leetcode.cn/problems/next-permutation/

先找末尾倒序的子串，然后将子串前一个字符和子串中，大于该数字的中，最小的那个进行替换。
然后利用双指针进行转置，这一步是我最开始没想到的。

关联目标：双指针刷题 9/76

42. 接雨水

拷贝一下别人的结题思路 https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0042.Trapping-Rain-Water/

每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，

关联目标：双指针刷题 10/76