two pointers 的很多问题，其实我们都是在维护两个 pointer 之间那个连续区间，作为我们的子问题。 而这两个 pointer 之所以可以单调移动，是因为其中一个指针所在位置，和后面区间所有元素组成的 pair ，都不是有效解。

双指针算法普遍分为三种

• 对撞类
  • two sum 类，partition 类
• 窗口类
• 并行型

例题：

76. Minimum Window Substring

Use a hashtable to track the chars in a window of source string labeled by two pointer and maintain a mini integer. And to check if the hashtable is valid for target string. If it's valid and if the substring of source is smaller than miniLen, we update our mini substring, than we move forward the left pointer to right, and update the source hashtable.

Missing Ranges

两根指针的变形题，维护两个变量，一个是prev 一个是cur，当两者之差大于1的时候，就往result里面加。

这题主要是有几个corner case要解决：

如何处理lower到第一个数，和最后一个数到upper的missing range？ 如何区分range中只有一个数和多个数？ 如何有效的得到missing range的起始和结束值，同时保证不会包含数组中的数字？

lower和upper 可以多两个循环来解决，假想在0 - nums.length - 1之外有 lower -1 和upper + 1 两个数。

本来如果不考虑头尾，那for循环本应是从1到length-1的，但是为了判断头，我们从0开始，将下标为0的数和lower-1比较得到第一个range。最后循环到length停止，当下标为length时，我们将当前指针指向upper+1，并判断upper+1和数组末尾是否能构成最后一个区间。

滑动窗口法 （窗口大小固定）

Substring with Concatenation of All Words

用hashmap 统计每个word出现的次数。 再用另外一个hashmap 去track每个word出现的个数，与此同时维护两个变量 count 和 left。

思路仍然是维护一个窗口，如果当前单词在字典中，则继续移动窗口右端，否则窗口左端可以跳到字符串下一个单词了。

出现不在字典的word以后，清空当前map重新开始统计。