双指针技巧分为两类：

  • 一类是“快慢指针（倚天剑）”，主要解决链表中的问题，比如典型的判定链表中是否包含环；
  • 一类是“左右指针（屠龙刀）”，主要解决数组/字符串中的问题，比如二分搜索。

一、快慢指针法-倚天剑

快慢指针一般会初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。

  1. 判断链表中是否有环

    经典解法双指针，一个跑得快，一个跑得慢。如果不含有环，跑的快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最后会超慢指针1圈，和慢指针相遇，说明链表含有环。

  2. 已知链表中含有环，返回这个环的起始位置

    解法：当快慢指针相遇时，让其中任何一个指针指向头结点，然后两个指针以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

    原因：假设第一次相遇时，假设慢指针slow走了k步，那么快指针走了2k步，得到快指针多了了一圈为k步。设相遇点与环的起点距离为m，那么环的起点与头节点head的距离为k-m，也就是说从head前进k-m步就能到达环起点。巧合的是，如果从相遇点继续前进k-m布，也恰好到达环起点。

  3. 寻找无环单链表的重点 笨方法：先指针遍历一遍，记录中节点个数为n，然后从头再来走n/2步 优雅解法：快指针一次走两步，慢指针一次走一步，当快指针到链表尽头时，慢指针就处于链表的中间位置。

    应用：寻找链表中点的一个重要作用就是对链表进行归并排序。对两部分链表分别排序，然后合并为有序数组。

  4. 寻找单链表的倒数第k个元素

    还是快慢指针，让快指针先走k步，然后快慢指针同时前进。快指针到链表尽头时，慢指针所在位置就是倒数第k个链表节点

二、左右指针法-屠龙刀

基本用法：一般初始化为left=0,right=len(num)-1

  1. 二分搜索

    左右指针在数组两端初始化，左指针往右走，右指针往做走，直至找到目标值

  2. 两数之和

    数组有序时，就应该想到双指针技巧。类似二分搜索，通过sum大小调节left和right的移动，直至找到目标对

  3. 翻转数组

    左右指针在数组两端初始化，相向而行，同时交互对应的元素

  4. 滑动窗口算法 双指针技巧的最高境界。快慢指针在数组/字符串上的应用。如果掌握了该算法，既可以解决一大类字符串匹配问题

三、左右指针法高级用法之-二分搜索算法(屠龙刀威力之一)

场景：给定一个数寻找左侧边界、寻找右侧边界

技巧：

​ 1）不要出现else，而是把所有情况用else if写清楚，这样可以清晰展现所有细节；

​ 2）计算mid时要防止溢出，推荐使用left + (right-left)/2，而不是(left + right)/2。

  1. 寻找一个数（基本二分搜索）

    数组排序为有序，左右指针根据大小判断左右指针依次相向而行，找到目标值

    差异梳理：因为我们初始化 right = num.length-1，决定了我们搜索区间是[left,right]

    所以决定了while(left <= right)，同时也决定了left=mid+1和right=mid-1

    因此我们只需要找到一个target的索引即可，所以当nums[mid] == target时可以立即返回

  2. 寻找左侧边界的二分搜索

    [1,2,2,2,3]返回下标1

    差异梳理：因为我们初始化 right = num.length，决定了我们搜索区间是[left,right）

    所以决定了while(left < right)，同时也决定了left=mid+1和right=mid

    因为我们需要找到target的最左侧索引即可，所以当nums[mid] == target时不要立即返回，而要收缩右侧边界以锁定左侧边界

  3. 寻找右侧边界的二分搜索

    [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问题(屠龙刀威力之二)

  1. 2Sum的核心解法

    笨方法：二重循环穷举，时间复杂度O(N2)，空间复杂度为O(1)

    优雅方法：用空间换时间，通过哈希表记录元素值到索引的映射，减少时间复杂度；

    2Sum问题就是想教我们如何使用哈希表解决问题

  2. 2Sum问题不重复结果对

    基本思路是排序加双指针，但是会出现结果重复。出问题的地方在于sum == target条件的if分支，当给res加入结果后，lo和hi在改变1的同时，还应该跳过所有重复元素。

  3. 3Sum问题

    笨方法：穷举

    优雅方法：使用遍历第一个数然后调用2Sum，关键点在于不能让第一个数重复，至于后面的2个数，复用的2Sum函数会保证他们不重复

    时间复杂度O(N2)

  4. 4Sum问题

    相同套路：穷举第一个数组，然后使用3Sum解决剩下3个数，然后组合出和为target的四元组。

  5. Num 问题

    首先对nums数组排序，然后n == 2时是2Sum的双指针解法，n > 2时就是穷举第一个数字，然后递归调用计算(n-1)Sum，组装答案