引言
假期在看这块知识时，突然想到双指针中的”快慢指针“就像是倚天剑，一前一后单向执行（就像倚天剑被灭绝师太和周芷若依次拿到那样），就是为了测试链表环的问题（为了测试武当七子连环阵的环是否有问题）；而”左右指针“就像屠龙刀，在使用时有一些前提：金毛狮王谢逊拿着时（数组有序啥的），然后用来进行二分搜索，加上递归解决Nsum问题，威猛无比
类比学习法而已，唯博君一笑耳！
双指针技巧分类：
双指针技巧分为两类：
- 一类是“快慢指针（倚天剑）”，主要解决链表中的问题，比如典型的判定链表中是否包含环；
- 一类是“左右指针（屠龙刀）”，主要解决数组/字符串中的问题，比如二分搜索。
一、快慢指针法-倚天剑
快慢指针一般会初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。
-
判断链表中是否有环
经典解法双指针，一个跑得快，一个跑得慢。如果不含有环，跑的快的那个指针最终会遇到
null，说明链表不含环；如果含有环，快指针最后会超慢指针1圈，和慢指针相遇，说明链表含有环。 -
已知链表中含有环，返回这个环的起始位置
解法：当快慢指针相遇时，让其中任何一个指针指向头结点，然后两个指针以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
原因：假设第一次相遇时，假设慢指针
slow走了k步，那么快指针走了2k步，得到快指针多了了一圈为k步。设相遇点与环的起点距离为m，那么环的起点与头节点head的距离为k-m，也就是说从head前进k-m步就能到达环起点。巧合的是，如果从相遇点继续前进k-m布，也恰好到达环起点。 -
寻找无环单链表的重点
笨方法：先指针遍历一遍，记录中节点个数为n，然后从头再来走n/2步
优雅解法：快指针一次走两步，慢指针一次走一步，当快指针到链表尽头时，慢指针就处于链表的中间位置。应用：寻找链表中点的一个重要作用就是对链表进行归并排序。对两部分链表分别排序，然后合并为有序数组。
-
寻找单链表的倒数第k个元素
还是快慢指针，让快指针先走k步，然后快慢指针同时前进。快指针到链表尽头时，慢指针所在位置就是倒数第k个链表节点
二、左右指针法-屠龙刀
基本用法：一般初始化为left=0,right=len(num)-1
-
二分搜索
左右指针在数组两端初始化，左指针往右走，右指针往做走，直至找到目标值
-
两数之和
数组有序时，就应该想到双指针技巧。类似二分搜索，通过sum大小调节left和right的移动，直至找到目标对
-
翻转数组
左右指针在数组两端初始化，相向而行，同时交互对应的元素
-
滑动窗口算法
双指针技巧的最高境界。快慢指针在数组/字符串上的应用。如果掌握了该算法，既可以解决一大类字符串匹配问题
三、左右指针法高级用法之-二分搜索算法(屠龙刀威力之一)
场景：给定一个数寻找左侧边界、寻找右侧边界
技巧：
? 1）不要出现else，而是把所有情况用else if写清楚，这样可以清晰展现所有细节；
? 2）计算mid时要防止溢出，推荐使用left + (right-left)/2，而不是(left + right)/2。
-
寻找一个数（基本二分搜索）
数组排序为有序，左右指针根据大小判断左右指针依次相向而行，找到目标值
差异梳理：因为我们初始化
right = num.length-1，决定了我们搜索区间是[left,right]所以决定了
while(left <= right)，同时也决定了left=mid+1和right=mid-1因此我们只需要找到一个
target的索引即可，所以当nums[mid] == target时可以立即返回 -
寻找左侧边界的二分搜索
[1,2,2,2,3]返回下标1
差异梳理：因为我们初始化
right = num.length，决定了我们搜索区间是[left,right）所以决定了
while(left < right)，同时也决定了left=mid+1和right=mid因为我们需要找到
target的最左侧索引即可，所以当nums[mid] == target时不要立即返回，而要收缩右侧边界以锁定左侧边界 -
寻找右侧边界的二分搜索
[1,2,2,2,3]返回下标3
差异梳理：因为我们初始化
right = num.length，决定了我们搜索区间是[left,right）所以决定了
while(left < right)，同时也决定了left=mid+1和right=mid因为我们需要找到
target的最右侧索引即可，所以当nums[mid] == target时不要立即返回，而要收缩左侧边界以锁定右侧边界。 又因为收缩左侧边界时必须left = mid+1,所以无论是left还是right，必须减1
逻辑统一：
对于寻找左右边界的二分搜索，常见的方式是使用左闭右开的"搜索区间"。我们还根据逻辑将"搜索区间"全部统一成两端都闭，便于记忆，好记，只要稍改nums[mid] == target条件处的代码和函数返回的代码逻辑即可，推荐拿小本子记下内容，作为二分搜索模板。
四、左右指针法高级用法之-Nsum问题(屠龙刀威力之二)
-
2Sum的核心解法
笨方法：二重循环穷举，时间复杂度O(N2)，空间复杂度为O(1)
优雅方法：用空间换时间，通过哈希表记录元素值到索引的映射，减少时间复杂度；
2Sum问题就是想教我们如何使用哈希表解决问题
-
2Sum问题不重复结果对
基本思路是排序加双指针，但是会出现结果重复。出问题的地方在于
sum == target条件的if分支，当给res加入结果后，lo和hi在改变1的同时，还应该跳过所有重复元素。 -
3Sum问题
笨方法：穷举
优雅方法：使用遍历第一个数然后调用2Sum，关键点在于不能让第一个数重复，至于后面的2个数，复用的2Sum函数会保证他们不重复
时间复杂度O(N2)
-
4Sum问题
相同套路：穷举第一个数组，然后使用3Sum解决剩下3个数，然后组合出和为
target的四元组。 -
Num 问题
首先对nums数组排序，然后
n == 2时是2Sum的双指针解法，n > 2时就是穷举第一个数字，然后递归调用计算(n-1)Sum，组装答案
