所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
- 使用同向双指针的场景之一是减少双重循环中的一些废操作，只保留精华部分
例如，解决滑动窗口类（连续子数组）的问题，首先，如果窗口大小是固定的k，那么这样的窗口在大小为N的数组有只N-k+1个（理解：考虑滑动窗口的起点，只能是从下标0开始到下标N-k结束）， 这样，其实可以一开始的时候，就构建一个k大小窗口，然后每次移动窗口，一共移动N-k次，花费N-k时间，所以固定大小滑动窗口时间复杂度是O（N）。很直观。
如果窗口大小不固定，那么，解空间上面，实际是存在N^2个窗口（连续子数组），理解：N个点任选两个点组合（除以2去除前后区别）就可以成为一个连续子数组。所以双重循环暴力求解情况下，时间复杂度是O（N^2）。
但是，如果滑动窗口存在某些特点，就可以使用双指针减少双重循环中的一些废操作，只保留精华部分，使时间复杂度由O（N^2）到O（N）。
例如，如果窗口左侧不变，向右每扩大一个元素，窗口的和（或者其他性质）都会增大，同时，满足窗口右侧不变，左侧增加，也就是窗口缩减的时候，窗口内的和（或者其他性质）都会减小。 那么，解题的套路就是，使用同向双指针，一开始left和right指针都指向第一个元素，然后， right向右走，某个时刻窗口从合法变到不合法了（或者不合法到合法），那停止right移动，此时只需要移动left。 这样，每次left和right都会至少移动一个，而left和right最多一起移动2N次，而每次移动花费时间1，所以时间复杂度是O（2N）。 left移动的过程里面，是不能超过right的，因为left就是永远指向窗口的左侧。结束条件就是right大于等于总长度，因为窗口的右侧不能越界。
这么分析还是有点抽象，这个问题的本质，就是在一个形状是三角形的解空间里面搜索一个目标。 如下，例如，在数组{4，2，3，1，5} 里面找到最小的连续子数组和，最接近且小于target = 8的数。
| left\right | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 4 | 6 | 9 | 10 | 15 |
| 1 | 2 | 5 | 6 | 11 | |
| 2 | 3 | 4 | 9 | ||
| 3 | 1 | 6 | |||
| 4 | 5 |
这个三角形，代表了以left为窗口左侧下标，right为窗口右侧下标的窗口总和情况。 那么，这个三角形有一个特点，就是每行从左到右是严格递增的，每列从上到下是严格递减的。 那么，找target为8的时候，可以先开始选一个起始的坐标，那就是（0，0），因为它往右走递增，往下走递减。 从4开始，走到9的时候，我们不用往右边走了，因为右边只会更大（也就是说这里我们进行了剪枝，去除了第0行9之后的所有元素）； 那下一步往下走，走到2，发现2是比8小，那么继续向右走，走到5，还是比8小，那么继续向右走（注意，这里的向右走其实也是剪枝，因为往下走的 话3是比5小的，不可能是答案，所以相当于排除去掉了第2行下面的所有元素）； 那么，同理，走到11的时候，发现比8大，那么从6向下走，到4，4在往下走到1，在往右到6，6不能走下去，而且6是最后一个元素，所以搜索结束。
这个访问的过程里面，每次记录下来，当前访问的元素和target的距离，答案一定就是其中最接近target的那个。 为什么时间复杂度是2N，也就是O（N）呢？因为left和right不会变小，而是直接就往右下角走去。也就是说，最多往下走N步，最多往右走N步。
在举一个类似的例子，这次例子不是求和，而是求窗口的AND。AND其实是有一个特点的，就是越AND越小，也就是说，左侧不动越往右越小，右侧不动， 左侧往右移动会越大。
假设，如下代表这样的窗口的AND值：
| left\right | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 9 | 8 | 7 | 6 | 5 |
| 1 | 10 | 9 | 5 | 7 | |
| 2 | 11 | 8 | 8 | ||
| 3 | 9 | 10 | |||
| 4 | 11 |
找小于且最接近target = 6.7的数，那么这次选则的起点还是选择（0，0）作为起点，但往左走变小， 往下走变大。 同理，花费2N找到答案。
PS. 连续子数组常用技巧就是先求前缀数组。
- 找两个点
方法就是左指针记录扫描过的某个特征的点，右指针扫描，然后每次减去左指针记录的值来得出答案的候选者，花费O（N）时间。
- 指向最后一个符合要求的值
例如，left永远指向下一个可用的位置，而left之前的值一定都是已经计算好了的值。
- 作为滑动窗口，left不动，right增加的时候，窗口增大的时候，要计算的结果不断的增大，直到不符合条件，这个时候再修改left。
具体题目
406(lintcode)和大于S的最小子数组
题意：数组中的元素都是正整数，求和大于S且最短的substring。
解：由于数组中的数都是正数，所以才能考虑使用滑动窗口双指针。因为多加一个元素就会有一个增长的趋势， 使用同向双指针，增大窗口，只要窗口的和大于等于s，那么就统计下长度，然后从左侧减小窗口的长度。 也就是说，right停止的时候，left到right的子数组和是第一个大于s的数， 也就是left到right - 1的子数组和是小于s的数，因此 往下走的时候（move left的时候），无论当前元素是否大于s，也不会往前走，因为前一个元素是必然小于上面元素的，也就是小于s的。
PS.如果是负数的，那么就没有增长趋势。也就是说窗口如何移动是不确定的。
283. Move Zeroes
题意：包含0的数组，将0移到最后面，注意非0必须保持原序（0不需要有序）。
解：使用同向双指针，类似于快排中按pivot分成两半的过程，这里的pivot就是0，不同的是不止一个0。
left指针指向放入下一个非0的空格的位置，right指针进行扫描，目的是找到所有的非0数，然后顺序放入left指向的位置。
具体：如果right遇到0，那么只++right，否则，将它们进行交换，其中不会出现不同值非0非0之间的交换。
所以，同一写成，发现right指向非0，那么就先swap left和right指向的元素，然后left和right都++。
75. Sort Colors
题意：数组里面只有三种数：0，1，2。现在要排序。不能使用counting sort，只能扫描数组一遍。
解：双指针。此题与只把0，1分开的那种pivot分两半过程的区别是，需要分为三半。 方法一：先根据0分两半，在把1和2分两半。不过需要遍历两遍。
方法二：使用双向双指针+一个扫描指针，left指向下一个放0的位置,也就是保证左侧都是0，right指向下一个放2的位置，保证其右边（不包括right自己）的为全2。
这样，在用一个指针从头扫描一遍后，所有的1将被挤在中间。
当前指针i如果指向的是0，那么与left交换，left++，同时当前指针前进一位，因为当前指针i >= left，说明left指向的部分已经被处理过了或者就是当前的0，所以被left交换到当前指针的元素不可能是2，而只可能是0或1，所以可以让i++。
当前指针i如果指向的是1，i++。
当前指针i如果指向的是2，那么与right交换，由于被交换过来的值可能是0，1，2，此时不能移动i，继续处理一遍i。注意：其中2的情况也不能动， 因为right永远指向的是下一个放2的地方，把2换到前面后，仍需要再被换到right后面来。
PS. 解法二也许应该叫三指针解法？
15. 3Sum
解：
2Sum的一个解法中使用了hash表，如果3Sum中仍然使用hash表，进行双循环，在hash里面找第三个数，那么时间复杂度是O（n^2)，空间复杂度是O(n)。
如果考虑到要O（n^2)以下的时间复杂度，那么可以先排序。然后，对数组中每一个数，把除了该数之后的数，当作解决一个2Sum的问题。 理解：每个元素遍历的时候，前面的元素已经都考虑过自己了，如果自己还考虑前面，那么重复了。
可以使用2Sum的hash解，也可以在2Sum中使用双指针的方法（空间复杂度降到O（1），相对低）。但总体时间复杂度都降到O（NlogN）。
注意：里面存在大量重复元素，因此需要设计去重。
如何去重： （1）对数组先排序，然后对每一个数遍历的时候，如果该数和上次遍历的数相同，那么不计算了。这样去除了相同元素重复计算的问题。
（2）计算2Sum的时候，不止有一个解，而且有些解是重复的，必须去除。去除方法是在找到一个解的时候，left向右看，有没有和当前left指向的元素相等的元素，如果有，那么直接left++，直到找到一个不相等的为止。对right进行类似操作。
PS.去除重复的问题基本都不会是计算完了再去，而一般都是一边计算，一边去除。
259. 3Sum Smaller
题意：整数数组，寻找三个元素和小于target的情况总数。
解：暴力求解显然是O（N^3）。优化技巧在于，在固定一个坐标的情况下，另外两个坐标的所有情况的寻找是否可以是O(N)时间，而不再是O（N^2）的时间。怎么优化双重循环暴力解呢，双指针。
技巧在于可以先排序。然后使用双指针。列出一个left，right的表，里面的值代表nums[left] + nums[right]。发现，右上角的元素往左边走变小，往右边走变大。 因此一开始搜索的元素就是left = 0, right = N - 1。
也就是使用双向双指针，如果一开始left和right指向的值加起来就比target小，说明所有的以left不变，到right的所有组合都比target小，此时将这些组合数纪录下并移动left； 反之，如果大于等于target，那么此时left不能移动，因为此left和之后的一些元素配合可能是答案，不能丢失掉，而移动right是没有这样的顾虑的，因为此right和任意的其他元素搭配必然超过target。 这样双指针O（N）的时间内就能求出这种两坐标的组合数。
42. Trapping Rain Water
题意：二维的坐标上有一些柱子（高度保存在数组中），求能收集的雨水的总量。第一个柱子和最后一个柱子存不了水。
解：发现每个柱子自己能积水的高度取决于其左侧最高柱子和右侧最高柱子两者中较矮的那个，使用暴力求解，对每个柱子向左右扫描，消耗时间O（N^2）。 如果有办法O（1）时间知道一个柱子左右两边最高的柱子，那么就可以把复杂度降到O（N）。 方法一：可以使用两遍扫描方法，每次扫描记录下每个元素的左右侧最高柱子高度，但这样需要花费O（N）空间。
方法二：使用双向双指针，分别指向数组两侧，往中间扫描，扫描的时候，使用两个变量记录扫描过的访问过的柱子里最高的左侧柱子LM和最高右侧柱子RM。中间的柱子在什么时候知道能收集多少雨水呢？考虑两个指针当前指向的柱子高度，首先知道，两个柱子灌水的高度上限就是LM和RM里面较矮的一个，
考虑两个当前指针指向的柱子高度，有一个较高的，一个较矮的，其中区别是矮柱子是可以计算解的，而高柱子是不可以计算解的，为什么？
因为矮柱子，我们知道它内侧已经存在比他高的柱子了，那么只需要在参考它外侧（扫描顺序的那一侧）的最高柱子（LM或RM），就可以计算储水高度了，如果它lM或RM那一侧的柱子并 不比当前矮柱子高，那么就说明该柱子无法储水。
相反，高柱子，我们在当前情况无法知道它是否能储水，因为它首先有可能就是最高柱子（指向高柱子的不会移动的）； 其次，如果不是最高柱子，虽然外侧没有柱子比它高，但是内侧是否有比它高的柱子存在是不知道的，因为无法计算。
在较矮柱子计算后，就可以继续移动它了，也就是说，两个指针指向的范围外是计算过的，被夹在双指针里面的是没有计算过的。
如果两个指针指向的柱子高度是相同的呢？此时移动哪一侧都行，因为，在发生等于情况之前，之前所有移动的柱子都比现在的高度矮。对吧？因为按照
我们移动矮柱子的策略。也就是说，对于相等的情况，两个柱子外侧都是比自己矮的柱子，也就是说，这两个柱子都无法储水。
407. Trapping Rain Water II
题意：基于42题，不过这次是三维空间上的收集雨水。
解：经过42题的分析我们知道，每个柱子能否有积水要看周围是否存在一整圈比自己高的柱子把自己包围住，且存储水的量取决于这些高柱子中最矮的那个。 因此扫描起点就是矩阵的外框。从外框向中间扫描的过程中，同42题的分析，要从离外框中最矮的柱子的柱子开始进行访问，因为它的结果是可以立即知道的。 为了找到外框中最矮的柱子，可以使用优先级队列。之后，找到该柱子一个最近的邻居点访问（上下左右四个方向），该邻居点一定不能是之前访问过的结点（建立一个hash表，标记访问过的结点）。
也就是说，整个扫描过程是类似BFS，但是使用的是优先级队列。
443. String Compression
题意：{“a”,”a”,”b”,”b”,”c”,”c”,”c”} 压缩成{“a”,”2”,”b”,”2”,”c”,”3”}，要求是O（1）空间。
其中，如果字符数量是1，那么只放字符本身，另外，如果字符数量大于10，那么按照若干字符来存放，例如10对应’1’， ‘0’。
解：此题的压缩方法是将字母重复出现的次数写在后面。
难点是考虑边界：例如{“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”} -> {“a”,”b”,”1”,”2”}。
要使用之前的数组空间（因为是压缩的，足够了），使用双指针，一个last指针指向要加入压缩后数组的新位置。然后，扫描，如果当前字符后面有相同的字符，那么新建循环(要新建！)将后面相同的字符吃掉，然后将数字加入压缩后的新位置。由于last指针要指向新数组的最后位置，所以要避免last = i的这种操作, 所以进行压缩的条件并不是last和i进行比较，而是i和i+1进行比较。
此题的启发：对关键信息进行下标锚定，例如此题就是对新出现的字符作为起点，与其后一个的字母进行比较的过程，其中需要单独处理没有后一个字母，也就是字母本身是最后一个字母的特殊情况。
PS. 字母出现一次，后面不能加1，因为可能会变更大。
532. K-diff Pairs in an Array
题意：给出一个k，求出数组（里面是整数）中差距为（相减的绝对值）k的数量。其中要求pair是不重复的，不是下标不重复，而是数字不重复，(i, j) 和 (j, i)算重复。
解： 难点在于去重。2sum的边扫描边存储的hash方法是不行的，因为那种属于下标不重复。
方法一：双指针。先排序，left和right指向0和1，left不能等于right（在left等于right的时候，right++），然后看双指针指向时候的差别，如果差别为k，那么res+1，left+1，然后看left是否和前一个left相等，如果相等要跳过（循环）。
方法二：hash。考虑将元素放入hash表，然后对新加入的元素进行比较。注意的是：{1,1,3}，k = 2， 其中{1,3}和{1,3}是重复的，因此，
对于这种情况，1和3的数量是不重要的，重要的是出现了1和3。但是也有特例，就是k = 0的情况。该情况下，数量变得重要起来，其中数量大于2，就说明找到一个pair。
因此，这样编码： 将每个元素存入hash表，value记录每个元素的数量；然后遍历该hash表：
（1）k不为0的时候，由于使用hash是无序的，所以只需要判断比元素大k（k是绝对值，不可以为负，需要在一开始判断）的元素的存在（数量不重要），不需要计算小k，否则计算出的是双倍的。
（2）k为0时候，需要看该元素是否出现两次以上，如果出现，那么就多了一种pair。
640. Solve the Equation
题意：解等式。
解：双指针，一个指向数字的开始，另一个从左到右扫描。如果遇到各种符号（遇到等号，那么后面的操作是反着的），例如遇到x，那么将前面的数字取出来，做一个系数计算。如果遇到的是加号减号，那么是计算常数的总和。
Java split方法小结：如果匹配的string里面不包括\转义符，那么基本上是正则表达式匹配。
代码中使用的exp.split(“(?=[-+])”);，其中？并没有加转义\，因此是正则表达式的元字符。 https://www.runoob.com/regexp/regexp-syntax.html ()的意思是分组，也就是把匹配括号内的情况保存起来。 ?= 的意思是正向看，也就是从开头或者+或-开始往右边看，遇到下一个+或-为止得出要的部分。 再结合()，意思是把2x, +3x, x, +7, -3 这种东西切出来。
3. Longest Substring Without Repeating Characters
题意：求substring中不含重复字母的最长的那个。
解：暴力求解当然是对所有的子串进行重复情况的扫描。但此题是有规律的，明显的，可以基于之前的子串，如果子串后的的字母是未曾出现的，那么直接加入计算，节省时间。
具体来说， 双指针维持一个窗口，窗口内是不重复的串。left和right一开始指向0，窗口大小为right - left + 1；
然后right++，先判断right是不是遇到一个重复字母c，如果是，那么先看倒数第二个c的位置（扫描中随时记录下每个字母的最右位置），
如果该位置落在当前窗口内（也就是比left大），那么说明窗口的起点需要更新到该位置+1的位置；否则不更新。实例：”abba”。
每次窗口右侧更新的时候，也就是扩张的时候，计算窗口的大小，并记录下其中最大的值作为最终结果。
PS. 1. 为什么不使用发现重复字母就计算一次窗口大小？
因为特例是整个字符串不包含重复字母。且如果单独考虑这种情况比较麻烦。
- 编码时候，结束条件是什么？
编码结束是right指针到头的时候，因为此时在增大left，对最终结果没有任何的影响。
680. Valid Palindrome II
题意：验证回文串，不过允许一个字符的差异，完美的回文串也行。
解：此题的第一反应是对每一个元素考虑去除掉剩下的进行验证，看是否回文，而且看本身是否回文。但是此解法时间复杂度为O(N^2)。
时间复杂度O(N)的算法如下：从两边向中间做正常的验证回文串的操作，但对失配的字符有容忍，例如在i和j处失配，那么如果去掉该字符后也回文，那么i+1处到j处一定回文，或者i到j-1一定回文，满足一个即可，都不满足那就不是回文串。
481. Magical String
题意：对于魔数，要求前i位的魔数中含有多少个1。所谓魔数，就是满足： （1）只含1，2
（2）连续的1和连续的2切开来看，数量是魔数本身。
例如：1 22 11 2 1 22 1 22 11 2 11 22， 对应1 2 2 1 1 2 1 2 2 1 2 2…
解：使用双指针，我们构造前i个魔数。构造技巧就是，我们构造的魔数中必然含有下一个魔数的信息，也就是说，我们构造1 22 11 2 1 22 1 22 11 2 11 22这种串，而这种串中蕴含了1 2 2 1 1 2 1 2 2 1 2 2…，我们根据1 2 2 1 1 2 1 2 2 1 2 2来构造1 22 11 2 1 22 1 22 11 2 11 22。 也就是说，双指针的其中一个指针t指向构造的魔数的尾部，另一个p指向下一个构造信息。 注意起始魔数是1 2 2，后面的可以根据规律推测。 实际示范：一开始给出1 22（第一个1表示1，第一个2表示22， 第二个2表示后面应该是两个数11或22）， 双指针p，t都指向第2个2，现在我们根据p指向的2进行构造：首先，指向2代表下一个连续的数量是2，但是是11还是22呢？这要看t指针指向的结尾是2还是1了，此时是2，所以是11，否则就是22。
487. Max Consecutive Ones II
题意：01串，只能翻转一个0到1，求最大连续1的长度。
解：第一反应是动态规划，但是动态规划会明显的多次扫描和消耗空间，而此题followup暗示是扫描一次就可以解决。
此题可以使用双指针来解。显然，此题只能使用同向双指针，也就是滑动窗口。更加通用的情况下，我们使用的滑动窗口可以包容k个0转1。右指针扩充的过程中，遇到0，那么使用掉一个0转1的机会，如果全部用完，那么统计当前窗口长度。之后左指针开始扩展，窗口收缩，如果左指针指向的是0，那么说明恢复一个0转1的机会，左指针停下，右指针又可以开始扩展了。
这种方法左指针访问了数组中之前的一个下标，但是followup是一个输入流，所以需要稍微做修改，修改的方法就是采用queue来存储之前访问的‘0’的位置，之后就可以从queue的头知道左指针该跳到哪一个位置了。 不能完全理解为什么使用同向双指针滑动窗口，就能解决这个问题，也许原因之一是滑动窗口从理论上包含了全部的解空间吧。
264. Ugly Number II
题意：计算第n个丑数，定义丑数为只能由2，3，5乘构造成。规定1是丑数。
解：此题解题思路就是依次的构造下一个丑数，得出第n个丑数。 构造规律如下：对于每个新生成的丑数，有三种可能扩充的情况：分别是乘2，乘3，乘5。 我们知道前5个丑数是：1，2，3，4，5，观察下面丑数生成的三个候选序列，下一个丑数一定是三个列表中生成出来的，也就是每一列的最小值：
(1) 1x2, 2x2, 2x2, 3x2, 3x2, 4x2, 5x2…
(2) 1x3, 1x3, 2x3, 2x3, 2x3, 3x3, 3x3…
(3) 1x5, 1x5, 1x5, 1x5, 2x5, 2x5, 2x5…
更新规律就是，每次比较最小的三个数，取出其中最小的作为最新的丑数，取出后，被取出的队列需要补充进去它的最后一个丑数乘以它的系数（2，3，5）。
为了实现这种结构：
（1）使用数组保存所有计算出的丑数；
（2）维持三个指针，分别指向（1）中的数组，含义是指向它的最后一个丑数。
还有一点要注意：会有重复的候选者。例如32和23，此时需要把两个全部取出。具体做法是：先计算出三个数中最小的，然后在看下三个数里面哪个等于最小值，如果等于，那么移动指针。
313. Super Ugly Number
题意：计算第n个超级丑数，超级丑数的定义是构成超级丑数的所有素数都在给定的素数列表中。1直接算一个超级丑数。
解：此题与丑数2解法一模一样，但是序列的个数是prime数组的大小，所以也就是k个序列的合并，在k个数中快速的找到最小值，可以使用priorityQueue。总体时间复杂度降为O(logk * n)。
再考虑去重技巧：大致思路是考虑入队列之前去重还是出队列时候去重。
入队列前去重：需要知道候选者中最小且重复的，这不太现实，因此排除这种方案；
出队列后去重：出队列的时候，把等于堆顶的元素全部出队列。这种就很简单，而且还不需要使用hash表这种去重机制。
522. Longest Uncommon Subsequence II
题意：与I相比，此题给出的字符串不止一个。LUS的定义: 不是其他任何字符串的子序列中最长的那个。 这也意味着LUS不一定存在。
解：对于I，解法就是返回两个字符串中较长那个（因为长的不可能为短的子序列），对于多个字符串是不是指最长的那个字符串呢？是的，不过最长的字符串有可能有两或多个一样的，该字符串不能作为结果，然后，只能考虑次长的串了，次长的且唯一的串一定就是答案吗？也不是，因为次长且唯一的串，有可能是之前最长串（不是答案串）的子串，在这种情况下，违反LUS的定义，不能作为答案。
所以，正确做法就是，先将给定字符串按长度从大到小排序(相等长度串按字符串大小排序)，然后从最长串开始看，看是不是与排在自己后面的串长度一样且自己在不在集合中，如果是，那么将自己加入集合，继续计算，之后一旦出现长度不一样，且自己不在集合中的情况，那么就开始与集合中每个串进行比较，看自己是不是其中一个串的子序列，如果是，那么直接退出，说明自己不是答案，如果全都不是，那么就返回自己作为答案。
暴力看一个串是不是另一个串的子序列使用就是直接用指针指向两个串的头，如果不等，那么移动大串的指针，两两比较，如果最后小串的指针到达末尾，说明是子序列，否则不是。
360. Sort Transformed Array
题意：给出一个已排序整数的序列，然后给出一个一元二次方程，将整数带入方程，求计算结果重新的排序，要求时间复杂度为O(n)。
解：此题要求O(n)时间复杂度，但是没有要求空间复杂度，因此可以考虑归并排序。回想一元二次方程的性质，在a > 0的时候，曲线是开口向上的，而给我们的序列是有序的，所以，如果可以想到双指针，那将可以解了，使用双指针指向序列的头尾，那么我们知道，两个指针向中间走，都是递减的（如果a < 0，那么就是递增的），因此可以使用归并排序。 如果a == 0,那么说明整个序列是线性的，仍会维持单增或者单减性质，所以不会影响归并排序。
524. Longest Word in Dictionary through Deleting
题意: 给出一个串S和单词字典d，S删除一些字符可以得到单词W，现在求W在字典中且是最长的（如果长度一样，那么返回字典序最小的那个）那个。
解：此题的删字母就是噱头，实际上，能不能删除得到，就是看单词是不是串S的子序列，这个使用双指针方法就可以了。
看起来最直接的解法就是，先将字典排序（长的排前面，一样长的按字典序排），然后一个个看是不是子序列，返回就可以，这种做法需要先排序。
排序花费时间O(klogk * len)，k是字典单词数，len是单词平均长度，然后扫描比较花费O(k * len)时间。
其实直接一遍扫描，保留当前的满足条件的最大值作为结果，看后面能不能更新这个结果就可以，花费O(k * len)时间。
159. Longest Substring with At Most Two Distinct Characters
题意：求字符串S的只含两个独特字符的子串中最长的那个。
解：此题使用滑动窗口，如果一直处于只含两个独特字符，那么窗口可以一直增大，如果遇到第三个特殊字符时候，那么需要把之前一个特殊字符给删除。 方法一：使用hashmap，记录字符和字符出现的次数，right不能扩展的时候，把left增加，然后看left字符在map中次数是不是减成了0，如果不是，那么继续移动left，否则就将left对应的字符删除。这样处理，直到map中的字符数量少于2个。
方法二：使用hashmap记录字符和当前字符出现的最靠右的下标，这样删除之前特殊字符的时候，可以先扫描一遍hashmap，然后取出其中最小的，然后更新left到它的下一个位置就可以了。
340. Longest Substring with At Most K Distinct Characters
题意：与159一样，不过子串里面只能包含k个特殊字符。
解：此题和159解法相同，只不过2写成k，而且k要注意是不是0，0的话直接返回。 每次找hash表中最靠左边的那个(leftMost)，删除掉该字符s[leftMost]，滑动窗口的left指针更新为leftMost+1。
287. Find the Duplicate Number
题意：一个n + 1大小数组中存放着1到n的正整数，其中只有一个正整数会重复（出现两次及以上），其余只出现一次（或者不出现）。
要求重复的是哪个数字，要求时间复杂度O(n^2)以内，空间复杂度O(1)。
解：此题重复的数可能不止一个，所以不能使用异或技巧。难点在于只能使用O(1)空间，所以不能使用hash。
解法一：先排序，然后扫描一遍，看相邻是否出现相等就可以了。
解法二：利用题目的特点，可以把正整数映射到下标。把正整数当作”指针”来看，例如正整数1，代表当前位置指针指向位置1。
这样，画出指针图后，此题就变成了证明链表是否存在环了。为什么？
首先，0的地方没有任何地方指回它，是入口。其次，如果是有两个数的指向同一个位置的话，那么，第一次这个数走到该位置后，
之后再通过链表依次访问，必然可以又走回到该位置，也就是说，第一次走入的是这个链表的环的入口。
质疑：（1）0处不是重复数字，从0走的时候，会不会走不到重复数字？例如，从nums[0]走到3，3的位置也是3。
答：num[0]能走到3恰好说明nums[0] == 3。依次类推，如果能走到一个数循环到自己位置，那说明前提是有重复数能够到达它。
（2）0处就是重复数字怎么办？
答：考虑最极端情况，0之后的数字都是独特的，且形成了链表。 那么画图发现，它们形成的链表其实就是一个大环，0处刚好就是入口。
因此，解法是快慢指针，先找到交叉点，然后快指针指向头变慢指针，最终走到一个公共点就是重复数字。相当于142题。
注意：一开始快慢指针都要指向开头0，这样判断条件就要写在while循环里面。
838. Push Dominoes
题意：推多骨诺米牌，左右推，求最终状态。
解：此题难点就是分析各种情况。对每个骨牌分别考虑，其实发现，影响这个骨牌的只有两侧离他最近的L和R，其余的对他不能有任何影响。
分为下面4种基本情况：
（1）左侧是L，右侧是R。这种情况下，骨牌不受力，是竖立的。
（2）左侧是L，右侧是L。这种情况下，骨牌受往左侧的力，向左倾倒。
（3）左侧是R，右侧是L。这种情况下，看R和L哪个近，离R近向右倒，离L近向左侧倒。
（4）左侧是R，右侧是R。这种情况下，骨牌受往右侧的力，向右倾倒。
再考虑开头和结尾的特殊情况：
（1）左侧不存在RL，右侧是L。此时向左倒。
（2）左侧不存在RL，右侧是R。骨牌不受力，是竖立的。
（3）右侧不存在RL，左侧是R。骨牌向右倒。
（4）右侧不存在RL，左侧是L。骨牌不受力，是竖立的。
其实，可以在左侧加入一个哨兵R，右侧加入一个哨兵L，这对真值表不造成影响，但是方便编程。
再考虑没有L或者R的情况：
（1）左右两侧不存在L或R。此时，骨牌不受力，是竖立的。
使用同向双指针。具体方法就是，用双指针指向每一对’L’或’R’字符的窗口。然后根据格子情况去一一对应处理。例如：.L.R…LR..L..，
为了处理边界情况，一开始在开头加入L，在结尾加R,转化为’R’.L.R…LR..L..’L’， 然后把它们看成R.L, L.R, R…L, LR, R..L， L..L。
双指针指的方式是这样的：对于LRLRL，left从0到n-2，right从1到n-1。找到新left之后，马上找下一个right。
243. Shortest Word Distance
题意：给出words单词数组，然后给出在单词数组里面的两个单词word1和word2，求word1和word2出现的最小下标距离，此题word1不等于word2。
解：word1和word2出现的下标可以组成自己的小数组，其中下标相邻的才可以进行计算，得出一个距离。
方法一：使用一遍扫描，扫描时候保持两个指针，一个指向之前访问的，表示是word1还是word2，然后，在当前指针扫描时候遇到与之前相反的情况， 那么就进行计算距离，最后得出一个最小距离返回。时间复杂度O(N)，空间复杂度O(1)。
方法二：使用两个hashmap(word1 -> vector
244. Shortest Word Distance II
题意：与243的区别是，此题要求写成类的形式，words数组作为类的参数传入。
解：此题相比较243题在于，空间本来就要O(n)，所以减小时间复杂度是首要考虑的点，使用243的方法二即可。
245. Shortest Word Distance III
题意：与243的区别是，此题word1和word2可以相等，但是不是当作0距离，而是要计算真正存在的两个单词。
解：此题相比较243题在于，一开始先判断单词是否相等，如果相等，那么单独处理，也是比较临近单词。
675.
1229. Meeting Scheduler
题意：两个人，每个人给出自己的开会可用的时间段数组（时间段用整数区间表示），另外，还给出两个人这次开会的时间长度d。 现在要求这两个人的这次开会的可行时间段中最早的。
解：此题如果暴力求解，也就是把区间进行两两比较，在维持一个最早区间候选者，那么时间复杂度显然是O(N^2)。
可以使用常见的技巧，也就是双指针技巧来优化这种双层循环的问题。显然，可以对两个区间分别进行排序。 其中越早的区间匹配了，那么可以提前返回了。例如，首先将区间根据起点排序。然后两个区间数组的第一个s1[0]和s2[0]进行比较： 如果它们有交集，且交集时间大于d，那么就是可以作为结果返回了；如果不满足条件，那么画出可能的三种情况（固定一个起点小的，然后扩充另一个）， 发现，其中结束点小的区间无法在配合任何区间组成结果了，因为对他来说最优的就是当前比较的区间，此时就移动这个数组的下标。 这样时间复杂度就减到了O(NLogN)。
PS.此题最有意思的地方就在于，一般题目的双指针是每次交替移动其中一个指针的一个位置，而此题则不一定，是每次移动满足条件的指针的一个位置， 时间复杂度仍是O(M+N)。
1099. Two Sum Less Than K
题意：整数数组A里面找出最小的一对，大小加起来小于给出的target。
解：先排序。之后此题解空间是一个二维矩阵，只考虑其中的一半（横坐标i小于纵坐标j的一半）。
然后对于其中，选择一个i = 0，j = len - 1为起点，特点是j往左走变小，i往右走变大。这样最多走len次就能得出答案。
这样缩减的原理就是，根据行列已经有序的特点，从而每次可以去掉j个或者i个结果，这样把时间复杂度降低到线性。
遍历时候，选择其中的比K值小的值中最大的值作为答案即可。
