Algorithm

两个指针-TwoPointer

[两个指针] (Two Pointer)

两个指针的题目主要分成三种情况：

a.对撞型

  1. 2Sum 类
    例题: Trapping Water
    一个指针i指向数组头，一个指针j指向数组尾。

    1
    2
    3
    4
    5
    6
    7
    while i != j:
      if num[i] < num[j]:
        i += 1
      elif num[i] > num[j]:
        j -= 1
      else:
        i += 1

  2. Partition类
    例题: 将一个数组分成两部分，一部分小与k，一部分大于k
    一个指针i指向数组头，一个指针j指向数组尾。i表示在i之前的元素都小于k，j表示在j之后的元素都大于k。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    while i != j:
      while num[i] < k:
        i += 1
      while num[j] > k:
        j -= 1
      if i > j:
        break
      else:
        swap(i, j)

总结
通过对撞型指针优化算法，根本上其实要证明不用扫描多余状态

b.前向型

  1. 窗口类
    例题: Minimum Window Substring
    窗口类指针模板j

    1
    2
    3
    4
    5
    6
    7
    8
    j = 0
    for i in xrange(n):
      while j < n: 
        if 满足条件:
          j += 1
          更新状态
        else 不满足条件:
          break

  2. 快慢类
    两个指针i, j的pace不同，可以用来探测一个链表是否有回路

总结
窗口类的问题根本上其实也是要证明不用扫描多余状态
快慢类的问题感觉和经常见的烧蜡烛的那种智力题很像。或者是环绕一圈来找list有没有cycle。

c.两个数组，两个指针

  1. 并行
    例题: Merge Two Sorted Array
    单纯的是否两个指针