数据结构与算法：线性表（三）—— 双指针

线性表中的双指针法是指通过两个指针（游标）来指示线性表中的元素的方法。双指针的使用本身并没有什么神奇之处，但是通过合适地操纵指针的移动，在某些特定问题中却能化腐朽为神奇，大大降低算法的时间复杂度。

根据对双指针不同的移动规则，整理了常用的双指针方法及其所用来解决的问题：

双指针法	操作说明	经典问题
首尾指针	使用两个指针指示线性表的首尾元素	二分查找、NSum
口袋指针	一个指针指示口袋口，另一个指针用于遍历	数组划分
窗口指针	两个指针指示窗口范围	窗口蠕动法求解连续子序列问题
快慢指针	使用两个移动速度不同的指针	环的检测和交点确定
早晚指针	使用出发时间不同的两个指针	消除距离差额
双表指针	两个指针分别指示两个线性表当前位置	数组归并

首尾指针

• 适用问题：需要同时操作首尾元素，或者需要指示变化中的线性表范围，使用首尾指针经常需要先对数组进行排序；
• 使用思路：
  • 指针含义：l指示线性表首部元素，r指示线性表尾部元素
  • 移动规则：依条件向内移动，直至相遇

反转线性表

• 问题：[344] 反转字符串，请编写一个函数，其功能是将输入的字符串反转过来；
• 思路：使用首尾指针交换元素，然后首尾指针向内移动，直至首指针不再小于尾指针；
• 代码：

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        l, r = 0, len(s) - 1
        res = list(s)
        while l < r:
            res[l],res[r] = res[r],res[l]
            l += 1
            r -= 1
        return ''.join(res)

• 分析：空间O(n)，时间O(n)

盛最多水的容器

• 问题：[11]盛最多水的容器，给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
• 思路：分治+首尾指针，问题首先划分为两个子问题，使用两侧较小边和不使用两侧较小边，然后取二者中的最大值；使用较小边时，容器两侧容纳最多的水，不使用较小边的子问题可以是原始问题的同类子问题，可以用递归求解，也可以用首尾指针来求，如果使用了较小边l，收集当前最大后l++，反之较小边为r则r—，直至l == r。

• 代码：

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l,r = 0,len(height) - 1
        res = 0
        while l < r:
            if height[l] < height[r]:
                res = max(res,height[l]*(r-l))
                l += 1
            else:
                res = max(res,height[r]*(r-l))
                r -= 1
        return res

• 分析：空间O(1)，时间O(n)

二分查找

# 闭区间写法:用[l,r]代表当前查找范围
def Binary_search(L,key):
    '''
    @L:有序数组
    @key:目标值
    @return:如果查找成功则返回目标元素索引，如果查找失败则返回目标值应插入的位置
    '''
    # 闭区间-初始化窗口
    l,r = 0,len(L)-1 
    # 闭区间-退出条件：窗口内不含元素，l=r+1，目标值在l,r之间
    while l <= r:
        mid = (l + r)//2
        if key == L[mid]:
            return mid
        elif key > L[mid]:
            l = mid + 1
        else:
            r = mid - 1

    return l

2 Sum

无序数组的 2 Sum

• 问题：[1] 两数之和，给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用
• 思路：使用哈希表存储元素残差，如果元素在哈希表则说明和为target，返回
• 代码：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i,num in enumerate(nums):
            if num not in d:
                d[target-num] = i
            else:
                return [d[num],i]

• 分析:空间O(n)，时间O(n)

有序数组的2Sum

• 问题：[167] 两数之和 II，给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2
• 思路：首尾指针法，如果量元素之和小于target则移动右移左指针，如果大于则左移右指针，如果相等，则返回两下标
• 代码：

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        low,high = 0,len(numbers)-1
        
        while low <= high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low+1,high+1]
            elif total < target:
                low += 1
            else:
                high -= 1

• 分析：空间O(1)，时间O(n)

3 Sum

• 问题：[15]三数之和，给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
• 思路：先排序+2Sum，先对数组进行排序，从前向后每次选取一个不同的元素x作为基准，然后在后面的数组中找到所有不重复的2Sum等于target-x的组合，再合并收集；保证解完备且不重复的核心有两点（选择下一个不同元素中的第一个）：①基准选择：每次选择下一个不同元素中的第一个，不同基准不会有重复解，第一个元素作为基准不会漏解②2Sum时：每次移动指针到第一个不重复的位置，也保证了2Sum的完备且不重复
• 代码：

  class Solution(object):
      def threeSum(self, nums):
          """
          :type nums: List[int]
          :rtype: List[List[int]]
          """
          nums.sort()
          n = len(nums)
          target = 0
          res = []
          for i in xrange(n-2):
              if i == 0 or nums[i] != nums[i-1]:
                  base = nums[i]
                  l,r = i + 1, n - 1
                  while l < r:
                      if nums[l] + nums[r] == target - base:
                          res.append([base,nums[l],nums[r]])
                          l,r = l+1,r-1
                          while l < r and nums[l] == nums[l-1]: l += 1
                          while l < r and nums[r] == nums[r+1]: r -= 1
                      elif nums[l] + nums[r] < target - base:
                          l += 1
                      else:
                          r -= 1
          return res       

• 分析：空间$O(1)$，时间$O(n^2)$

N sum

• 问题：[18] 四数之和，给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组
• 思路：排序+递归+2Sum，NSum可以转化为N-1Sum，逐步转化为2Sum，类似的只要每次选取下一个不同元素中的第一个元素，就能保证最终解的完备且不重复
• 代码：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def NSum(nums, target, N):
            n = len(nums)
            if n < N or nums[0] * N > target or nums[-1] * N < target:
                return []
            res = []
            if N == 2:
                l,r = 0, n-1
                while l < r:
                    if nums[l] + nums[r] < target:
                        l += 1
                    elif nums[l] + nums[r] > target:
                        r -= 1
                    else:
                        res.append([nums[l],nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]:l += 1
                        while l < r and nums[r] == nums[r+1]:r -= 1
                return res
            else:
                for i in xrange(n-N+1):
                    # 核心，保证了两轮解中不包含重复解
                    if i == 0 or nums[i] != nums[i-1]:
                        for pre in NSum(nums[i+1:],target-nums[i],N-1):
                            res.append([nums[i]] + pre)  
                return res
            
        return NSum(sorted(nums),target,4)

• 分析：空间$O(1)$，时间$O(n^{N-1})$

最接近的三数之和

• 问题：[16. 最接近的三数之和]给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
• 思路：排序后转化为2Sum，收集绝对差值最小的组合
• 代码：

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n = len(nums)
        if n < 3:
            return None
        
        nums.sort()
        res = None
        delta = float('inf')
        for i in xrange(n-2):
            if i == 0 or nums[i] != nums[i-1]:
                l, r = i + 1, n-1
                while l < r:
                    cur = nums[i] + nums[l] + nums[r] - target
                    if abs(cur) < delta:
                        res = [nums[i],nums[l],nums[r]]
                        delta = abs(cur)
                    if cur == 0:
                        return target
                    elif cur > 0:
                        r -= 1
                    else:
                        l += 1

        return sum(res)

口袋指针

• 适用问题：将数组中满足条件的元素移至一端，要求原地修改且满足条件的元素相互位置保持稳定；
• 使用思路：假想用一只“袋子”盛放满足条件的元素，初始时袋子为空，用l=-1指示袋子口的位置，使用另一个指针从0开始遍历整个数组，如果当前元素满足条件，则袋口+1，将当前元素通过交换放入袋中，当遍历结束时，所有满足条件的元素就都被放入到袋子中了。

移动 0

• 问题：[283] 移动零，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
• 思路：口袋指针法，初始口袋口-1，遍历整个数组，如果元素不等于0，袋口扩充，并将该元素和袋口元素交换
• 代码：

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = -1
        for j in range(len(nums)):
            if nums[j]:
                i += 1
                nums[i],nums[j] = nums[j], nums[i]

• 分析：空间O(1)，时间O(n)

红白蓝划分

• 问题：[75] 分类颜色，给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色
• 思路：两次口袋指针法，先把0放头部，再把1放0后面数组的头部；或者使用首尾两个口袋，一次遍历将0放头口袋，将2放尾口袋
• 代码：

class Solution(object):
    """
    思路1：使用前后指针，口袋交换法，将等于0的交换至前面，将等于2的交换至右边
        开区间表示两次装袋
    思路2：双边装袋，略显复杂，还不如遍历两次
    """
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i,j = -1,n
        k = 0
        while k < j:
            if nums[k] == 0:
                i += 1
                nums[k],nums[i] = nums[i],nums[k]
                k += 1
            elif nums[k] == 2:
                j -= 1
                nums[k],nums[j] = nums[j],nums[k]
            else:
                k += 1

• 分析：空间O(1)，时间O(n)

快排划分

• 问题：选取首元素作为枢轴值，将数组中小于等于该值的元素交换至头部，大于该值的交换置数组尾部，返回枢轴值最终的位置
• 思路：口袋指针法
• 代码：

def partition(A,low,high):
    """
    在A[low:high+1]中选取枢轴点，并按首轴值排序
    """
    i = low                         
    for j in xrange(low+1,high+1):
        if A[j] <= A[low]:
            i += 1
            A[i],A[j] = A[j],A[i]
    A[i],A[low] = A[low],A[i]
    return i

• 分析:空间O(1)，时间O(n)

寻找第k大

• 问题：[215] 数组中的第K个最大元素,在未排序的数组中找到第 k 个最大的元素
• 思路：有很多方法可以求解此问题，但最高效的方法是口袋指针法，类似于快排划分，将首元素(先做随机交换)作为枢轴值，将所有大于等于它的元素交换至数组头部，返回数轴值最终位置pivot，如果枢轴值位置刚好是k-1，则说明该位置的值即为第k大的值，如果i k-1，在左半边nums[:i]寻找第k大
• 代码：如果枢轴值不进行随机选择，效率还不如先排序！！

import random
class Solution(object):
    """
    思路1：先排序，时间O(nlgn)
    思路2：建立大根堆，弹出第k个O(n+klgn)
    思路3：口袋指针法，平均O(n)，以首元素为枢轴值，进行划分
        1. 如果数轴位置i==k-1则直接返回i对应的值
        2. 如果i <k-1,在有半部分nums[i+1:]寻找k-i-1大
        3. 如果i > k-1，在左半边nums[:i]寻找第k大
    """
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        if n < 1 or n < k:
            return None
        if n == 1:
            return nums[0]
        
        pivot = self.partition(nums,0,n-1)
        if pivot == k - 1:
            return nums[pivot]
        elif pivot < k - 1:
            return self.findKthLargest(nums[pivot+1:],k-pivot-1)
        else:
            return self.findKthLargest(nums[:pivot],k)
        
    
    def partition(self,nums,low,high):
        rand = random.randint(low,high)
        nums[rand],nums[low] = nums[low],nums[rand]
        bag = low
        for i in range(low+1,high+1):
            if nums[i] >= nums[low]:
                bag += 1
                nums[bag],nums[i] = nums[i], nums[bag]
        nums[bag], nums[low] = nums[low],nums[bag]
        return bag

• 分析：最好情形$T(n)=T(n/2)+O(n)$，空间复杂度O(lgn)，时间复杂度为O(n)

窗口指针

包含剪枝条件的连续子序列问题：

1. 连续子序列问题：求解满足条件f的连续子序列；
2. 包含剪枝条件：如果在找到了一个首次满足特定条件g的连续子序列之后，发现可以排除掉(l<=xr)部分的解，就可以左移连续子序列的左侧边界l直至条件g不再满足，即(l’<=x,r<=y)不能排除；

常见的这类问题有：

1. 满足条件的最长连续子序列问题；
2. 满足条件的最短连续子序列问题；
3. 内在的满足剪枝条件的其他类型连续子序列问题；

窗口蠕动法：将连续子序列看做是一个“窗口”，用左右指针l,r来标识窗口，起初窗口为空(l=0,r=-1)，备选解解存在于(x>=l,y>r)，每次通过右移右指针来扩展窗口(l,r)，如果当前窗口满足上述减枝条件g，则通过右移左指针实现剪枝(l’,r)，移动过程中收集满足条件f的解，剩余备选解在(x>=l’,y>r)中，循环以上过程得到所有满足条件的连续子序列。因为窗口移动的过程通常是由右指针来扩展，由左指针来收缩，很像虫子向前蠕动的过程，因此叫窗口蠕动更形象。

窗口蠕动包含三个步骤：扩展-剪枝-收集（核心是设计出合适的减枝条件）

1. 初始化空窗口l=0,r=-1
2. 循环以下过程直至右指针越界
   1. 扩展：右移右指针
   2. 剪枝：如果达到下一个可剪枝的窗口，则右移左指针，直至不能再剪枝
   3. 在窗口满足条件时收集备选解
3. 返回最终解

满足条件的最长连续子序列

无重复最长子串

• 问题:[3] 无重复字符的最长子串，给定一个字符串，找出不含有重复字符的最长子串的长度

• 思路：当窗口首次包含重复时，(r>x>l,r>y>l)(不是最长)以及(x=l,y>r)(包含重复)部分可以剪枝，右移左指针直至包含重复

  • ① 初始化窗口l=0,r=-1
  • ② 循环以下过程直至右指针越界r==n
    • 右移右指针
    • 如果当前窗口包含重复，右移左指针，直至当前窗口不包含重复
    • 更新不包含重复字符的子串的最大长度
  • ③ 返回最大长度

• 代码：

from collections import Counter
def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    n = len(s)
    dic = Counter()
    res = 0
    l = 0
    for r in xrange(n):
        dic[s[r]] += 1
        while dic[s[r]] > 1:
            dic[s[l]] -= 1
            l += 1
        res = max(res,r-l+1)
    return res

• 分析：空间O(n)，时间O(n)

满足条件的最短连续子序列

和大于s的最短子数组

• 问题：[209] 长度最小的子数组，给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组。如果不存在符合条件的子数组，返回 0
• 思路：当窗口和首次大于等于s时，(r>x>l,r>y>l)(小于s)以及(x=l,y>r)(不是最短)部分可以剪枝，右移左指针直至窗口和小于s
  • ① 初始化窗口l=0,r=-1
  • ② 循环以下过程直至右指针越界r==n
    • 右移右指针
    • 如果当前窗口和>=s，更新最短数组的的长度，右移左指针，直至当前窗口<s
  • ③ 返回最大长度
• 代码：

def minSubArrayLen(self, s, nums):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    cur = 0
    res = n + 1
    
    i = 0
    for j in xrange(n):
        cur += nums[j]
        while cur >= s:
            res = min(res,j-i+1)
            cur -= nums[i]
            i += 1
            
    return res if res <= n else 0

• 分析：空间O(1)，时间O(n)

最小覆盖子串

连续序列覆盖子串问题是一类非常经典的问题，值得认真体会，关键点有两个：

1. 剪枝条件：当已经覆盖时，可以剪枝，l右移至不再覆盖，即第一次need[s[l]]从0变成1的时候
2. 用count和need标识总需求和每个字符的需求数：count=0时表示已经覆盖，need为负数时表示已超出需求

• 问题：[76] 最小覆盖子串，给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

• 思路:当窗口首次覆盖子串时，继续扩展r不是最优，(l,r)内不能覆盖，可进行剪枝，右移l直至不再覆盖，不再覆盖不好判断，但不再覆盖的前一位置可以判断。用count统计当前窗口还缺多少个字符，用need记录当前每种字符需求数，如果是负数代表多余个个数。（覆盖问题使用need存放每个元素的需求，使用count存放总需求对于剪枝判断是个很好的技巧，下面我们还会反复遇到）
• 代码：

def minWindow(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    count,need = len(t), Counter(t)
    l, L, R = 0, 0, -1
    for r, c in enumerate(s):
        count -= need[c] > 0
        need[c] -= 1
        while count == 0:
            if R == -1 or r - l < R - L:
                L, R = l, r
            need[s[l]] += 1
            count += need[s[l]] > 0
            l += 1
                
    return s[L:R+1]

-分析：空间O(n)，时间O(n)

最小区间

• 问题:[632] 最小区间， 你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小

输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释: 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

• 思路：同最小覆盖子串，核心在于如何判断刚好已覆盖和刚好未覆盖，将所有值按照(值,所属分组号)排序，在排序后的数组上进行窗口滑动，当刚好都覆盖时进行剪枝，同时收集最优结果，右值l直至刚好不再覆盖。
• 代码：

from collections import Counter
def smallestRange(self, nums):
    """
    :type nums: List[List[int]]
    :rtype: List[int]
    """
    count = len(nums)
    need = Counter(range(count))
    p = [(val,i) for i in xrange(count) for val in nums[i]]
    n = len(p)
    p.sort()
    
    l = 0
    res = [p[0][0],p[-1][0]]
    for r in xrange(n):
        count -= need[p[r][1]] > 0
        need[p[r][1]] -= 1
        while count == 0:
            if res[-1] - res[0] > p[r][0] - p[l][0]:
                res = [p[l][0],p[r][0]]
            need[p[l][1]] += 1
            count += need[p[l][1]] > 0
            l += 1
    return res

• 分析：涉及到排序，空间O(n)，时间O(nlgn)

其他包含剪枝的连续子序列问题

包含字符串的排列

• 问题：[567] 字符串的排列，给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列
• 思路：窗口蠕动法，只要s2的某个子串的字符统计量等于s1的字符统计量，即返回True。该问题包含减枝条件，当加入的字符统计量超出s1的需求时可以剪枝，右移左指针直至不超，此时判断s1的需求数是否刚好满足，满足则返回True（不多、又刚好满足需求），否则继续扩展窗口。仍然使用need代表每个元素的需求数，用count代表总体需求数。
• 代码：可以看到，代码与上面两题基本上相同

def checkInclusion(self, s1, s2):
    """
    :type s1: str
    :type s2: str
    :rtype: bool
    """
    count,need = len(s1),Counter(s1)
    l = 0
    for r,c in enumerate(s2):
        count -= need[c] > 0
        need[c] -= 1
        while need[c] < 0:
            need[s2[l]] += 1
            count += need[s2[l]] > 0
            l += 1
        if count == 0:
            return True
    return False

• 分析：空间O(n)，时间O(n)

乘积小于K的子数组

• 问题：[713] 乘积小于K的子数组，给定一个正整数数组 nums，找出该数组内乘积小于 k 的连续的子数组的个数
• 思路：直接应用窗口移动法时，不满足剪枝条件，因为(l<x<r,x<=y<r)这部分不能被剪掉，但如果这一部分已被统计过了，就仍然可以正常剪枝。当窗口满足条件时，我们统计以r结束的满足条件的连续数组个数，当r放入后如果不满足条件，我们就可以进行正常的剪枝了，因为后面的肯定不满足，前面的已经被统计过，此时只需要将l移至下个满足条件的位置即可。
• 代码：

def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        i,j,count,prod = 0,0,0,1
        while i <= j < n:
            j += 1
            prod *= nums[j-1]
            while i < j and prod >= k:
                prod /= nums[i]
                i += 1
            count += j - i
        return count

• 分析：空间O(1)，时间O(n)

区间子数组的个数

• 题目：

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。

求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入: 
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].

• 思路：

class Solution(object):
    """
    思路：窗口滑动法，窗口为满足条件的子数组，统计收集窗口内以右指针为末尾且满足条件的子数组个数count，移动右指针
        1. 如果新元素在范围内那么以新元素为末尾的满足条件的子数组个数为j-i+1
        2. 如果新元素小于L，那么以新元素为末尾的子数组为count
        3. 如果新元素大于R，那么不可能以新元素为末尾，移动左指针到新的位置j+1
    """
    def numSubarrayBoundedMax(self, A, L, R):
        """
        :type A: List[int]
        :type L: int
        :type R: int
        :rtype: int
        """
        res = 0
        count = 0
        l = 0
        for r in xrange(len(A)):
            if L <= A[r] <= R:
                res += r - l + 1
                count = r - l + 1
            elif A[r] < L:
                res += count
            else:
                count = 0
                l = r + 1
        return res
        

快慢指针

快慢指针：使用移动速度不同的两个指针slow,fast(通常fast移动速度是slow的两倍)来遍历线性表。

环形检测：如果线性表中存在环，那么快慢指针从同一起点出发，如果能够再次相遇，则说明线性表中存在环。

寻找中位数：快慢指针同时从线性表首元素出发，当快指针无法前进时，慢指针会指向下中位。

链表中用的最多，比如[141] 环形链表，[142] 环形链表 II，[234]回文链表，详情参考链表，这里仅讨论在顺序表中的使用

寻找重复数

• 问题：[287]寻找重复数，给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次

• 思路:1~n的n+1个整数组成的数组，可以看作是一条静态链表，下标0代表头指针，列表中的值代表next指针，类似于链表中寻找环的交点算法，可以找到数组中的重复元素
• 代码：

  def findDuplicate(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      n = len(nums)
      slow = fast = 0
      # 首先找到下一个交点
      while True:
          slow = nums[slow]
          fast = nums[nums[fast]]
          if slow == fast:
              break
      # 排除另一个慢指针，与上一个慢指针同时出发，交点即重复元素
      slow2 = 0
      while True:
          slow = nums[slow]
          slow2 = nums[slow2]
          if slow == slow2:
              return slow

• 分析：空间O(1)，时间O(n^2)

早晚指针

早晚指针：在指针移动某位置时，另一个指针从头出发，主要用处在于产生/消除差额。

使用快慢指针判断环的交点问题中也使用到了早晚指针，另一个经典的应用是寻找链表中倒数第k个节点，原理是当第一个指针移动了k次时，再派出一个指针从头开始同步移动，最后当早指针不能前进时，晚指针指向的就是倒数第k个节点。

双表指针

• 指针含义：两个指针分别用于指示两个线性表中的当前位置
• 指针移动：具体问题具体分析
• 问题特点：当需要同时操作两个线性表时，典型的有数组归并，链表逆序

数组交集

• 问题：[349] 两个数组的交集，给定两个数组，写一个函数来计算它们的交集
• 思路：该问题使用集合很容易在O(n)时间复杂度下求解，如果不使用集合，可先对数组排序，用两个指针指示两个数组的出现不同元素的第一个元素，如果相等则收集，直至其中一个遍历完。虽然是一种笨的方法，但用到的方法在很多问题中都会遇到。
• 代码：

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        m,n = len(nums1),len(nums2)
        res = []
        i = j = 0
        while i < m and j < n:
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i,j = i + 1, j + 1
                while i < m and nums1[i] == nums1[i-1]: i+= 1
                while j < n and nums2[j] == nums2[j-1]: j+= 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                i += 1
        return res        

归并排序

详见链表或者排序

链表逆序

详见链表