Unit 4 九章高级算法课: Two Pointers

标签（空格分隔）： leetcode TwoPointers 九章

[TOC]

2根指针有3种题型:

  1. 一个数组, 从两边向中间移动(对撞型)
  2. 一个数组, 同时向前移动(前向型)
  3. 两个数组(并行型)
  4. 重点是记住: 模版是死的, 人是活的. 不要拘泥于模版. 参见min Substring contains target把题做少, 即所有新题都往会的方法上面靠.

对撞型

inspired by Qsort's partition. 有2个类型的题目:

  1. 2 sum
  2. partition
  • 模版
  • Two sum模版
int i = 0, j = leng-1;
while (i < j) {
    if (a[i] + a[j] > sum) {
        do something
        j--;
    }
    else if (a[i] + aj] < sum) {
        do something
        i++;
    }
    else {
        do something
        i++/j--/
}
  1. 灌水模版
int i = 0, j = leng-1;
while (i < j) {
    if (a[i] > a[j]) {
        do something
        j--;
    }
    else if (a[i] < a[j]) {
        do something
        i++;
    }
    else {
        do something
        i++/j--
}
  1. 总结模版
int i = 0, j = leng-1;
while (i < j) {
    if (A[i]和A[j]满足某个条件) {
        j--;  // 直接跳过k ∈ [i+1, j-1] 和j组成的pair, 这需要证明. 也是O(n^2)-> O(n)的关键. 
        do something
    }
    else if (A[i]和A[j]不满足某个条件) {
        i++; // 直接跳过i和k E [i+1, j-1]组成的pair.
        do something
    }
    else {
        do something
        i++或者j--.
    }
}

Trapping water area

  • container with most water

  • 方法1: brute force.

    • 通过2层循环, 找到每一个pair组合构成的面积. O(n^2).

  • 方法2: 灌水型的都想到对撞型指针.

    • 条件是什么呢? 这里有个数学分析: 先找到l/r里面的短板. 那么重点来了: 不用循环i跟[i~j]的板子组成的container. 因为面积由短板决定. 所以若[i~j]之间有比i更小的板, 那么面积只会是heights[k] (k-i). 所以比[i,j]组成的小. 或者, 如果[i~j]之间有比i大的板子, 那么面积也只会是heights[i] (k-i). 因为k < j. 所以更小. 于是证明了, 每次只要找到短板构成的面积, 然后和全局res来update.

前向型

2类题目:

  1. 窗口类: 注意和sliding window不同, sliding window是给定了窗口大小, 找一个符合条件的窗口; 而two pointer的窗口型是指大小不确定, 找一个符合条件的窗口. 所以前者使用heap, deque维护. 后者通过指针来维护.
  2. 快慢类
  • 模版:
    int i,j;
while (i < leng) {
  while (j < leng) {
      if (满足条件) {
          更新结果/HashMap
          j++;
      }
      else {
          break;
      }
  }
  更新结果/HashMap
  i++;
}

Minimum Window Substring contains target string in source

题目: Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n). S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”.

  • 类似题目: longest substring with at most k distinct characters

  • Key: 重点在于理解前向型双指针的算法思想. 而不是生搬硬套九章模版(应该适当修改). 学习如何用HashMap来作为数组存在判定.

  • 分析: 我一开始按照九章的前向型模版套着写的, 很简单, 但是也不太好. 因为每一次都要对256个数字判断. 所以Time complexity是O(256N). 老师讲了用source hash - target hash的方法. 但是我写的有错. 不知道怎么处理找到window的时候怎么去掉第一个char, 以及更新状态(即所有全局变量).

  • 然后搜到了Leetcode的答案, 以及Rui Bi精彩的Java实现. 其实就是前向型双指针的使用, 不过和template有点小小区别.

    • 意思如图: . 关键在于实现. 特别是找到window之后, 怎么advance pointer以及更新状态?

  • 代码如下

    /**
   * http://xmruibi.github.io/2015/10/08/minimum-window-substring/
   * http://articles.leetcode.com/2010/11/finding-minimum-window-in-s-which.html
   */
  public String minWindow(String source, String target) {
    // preload for target checking
    if (source == null || source.length() == 0 || target == null || target.length() == 0) return "";

    int tarLen = target.length();
    HashMap<Character, Integer> dict = new HashMap<>();  // target hash
    for (char c : target.toCharArray())  // 简洁
      dict.put(c, dict.containsKey(c) ? dict.get(c) + 1 : 1);  // 好写法!

    int hitCount = 0; // record current window hits how many characters in target
    int l = 0; // record the left bound of current window
    int minWindow = source.length() + 1; // initial the minimum window length
    int start = 0;  // hold the global left bound of min window
    for (int r = 0; r < source.length(); r++) {
      char cur = source.charAt(r);  // 因为只考虑一个char, 所以保存起来, 避免每次都用charAt求.

      if (!dict.containsKey(cur)) continue;  // 若不符合, 就找下一个点.即增加right.

      dict.put(cur, dict.get(cur) - 1);    // 更新Target hash. 注意这个也同时表示了Diff hash. 即当前window和target hash之差. 所以找到一个window并不是说Target hash全为0. 例如AAAABC里面找ABC. 则第一个window就会导致Thash的A为-3.
      if (dict.get(cur) >= 0) hitCount++;  // 关键之一: 通过Target hash, 判定是否已经找到了一个有效字符. 负数的次数也是有用的, 表明当前window有多于target的target[j]. 这在前移left的时候用到.

      // check the windows has amount of this char more than it in target string
      // loop until the amount back to normal, but always reduce the prev index char
      while (hitCount == tarLen) {  // 满足条件的情况.
        if (minWindow > r - l + 1) {
          start = l;
          minWindow = r - l + 1;
        }
        char prevChar = source.charAt(l);
        if (dict.containsKey(prevChar)) {  // hashmap比int[256]好处在于存在就是target里的char.
          dict.put(prevChar, dict.get(prevChar) + 1);  // 关键2: 如何更新状态? 恢复dict即说明下一次for要继续找到prevChar.
          if (dict.get(prevChar) > 0) hitCount--;  // 当Target hash里面有正数个prevChar, 那就要找这个char, 于是hitcount恢复为自减1.
        }
        l++;
      }
    }
    //
    if (minWindow > source.length()) return "";  // 注意如果没找到, 应该回复空.
    return source.substring(start, start + minWindow);
  }