Double pointers
当题目要求我们的时间复杂度为O(n)的时候，有什么工具可以用吗？
hash
-
double pointer～
double pointer 又分成多种形式(可能还有其他形式，待补充)
(1) 从两边往中间靠拢，不断缩小范围
- 移动对象
有的是每次只移动left 或 right 中的一个，
有的是一起移动。 - 怎么移动
一次一步
一次多步，直到符合某种条件为止，而且要考虑最后需不需要继续补上一步
(2) 一起从左往右移动
- 方式1：
while(left<s.length() && right<s.length())
- 移动对象
right++ 直到符合某个条件A
left++ 直到符合某个条件B
进行操作C
* 方式2：
for( left = 0; left < s.length(); left++)
{
right ++ 直到符合某个条件A
每次判断一下left是否符合条件B
如果符合条件B，进行操作C
}
方式1的效率会比方式2直观些。
leetcode 题目
76 Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
给出两个字符串，在s 里面找出包含t的所有字符的，长度最短的，子串～我们也叫他词窗好了(__)
时间复杂度是n
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
思路
什么是符合要求的条件？怎么找到符合条件的区间？ 需要怎么样的时间复杂度？
符合条件的区间就是解了吗？需不需要继续调整？
用什么判断是否为符合条件的解?
有多个解吗？
解决方案
按照题目要求，子序列里面要包含目标字符串里面的所有字符，指的是不仅仅包含该字母，而且对应字母出现的次数不能低于目标字符串里面的。
有什么方法可以快速找到这种对应关系？ --> 用hashmap记录窗口里面的信息 以及 target字符串的信息。
-
得先找到符合条件的区间：
> while（！valid_window） > modify hashmap of the window > right++ 符合条件的区间就是解了吗？--> 想想字符出现顺序的影响？
-
题目有没有什么其他限制？ --> 题目要求最短的子串
从 4 & 5 得出结论 --> --> 需要缩词窗
while（valid_window）
modify hashmap of the window
left++
在哪里更新解？
容易错\画蛇添足的地方
（1）在right指针移动完之后，判断是否最优解 --> 没必要，因为这个解可能有冗余，后面还会移动left指针
（2）在移动left指针的过程中，判断是否最优解 --> 没必要，本来就没消除完冗余
（3）在移动玩了left指针之后，left 在那里？ 这时候，left 对应的已经是越过了 solution 左边界的地标，我们需要 left-1来指到目标解的起点。
注意的细节
（1） 题目要求的是包含关系，对序列内的顺序没有要求
（2）HashMap在使用上，要注意更新操作、以及先检查有无包含，再get
可以优化的地方
（1）由于我们只是处理字符，而Java中 char字符为8位编码，所以没必要用hashMap, 直接使用数组，速度可以得到大幅度提升。
11. Container With Most Water
思路
- Capacity = min(height[left], height[right]) * (right-left)
- 每次移动都是为了找到possible Max Capacity
- (right-left) 必定是不断缩小的
- 所以我们关注的是 height[left] 和 height[right]
- 移动的时候可以加入 while 判断来节省时间
具体代码
public int maxArea(int[] height) {
if(height.length==0)
return 0;
int left = 0;
int right = height.length-1;
int ans = 0;
while(left < right)
{
int min_h = Math.min(height[left], height[right]);
ans = Math.max(ans, (right-left)*min_h);
if(height[left] < height[right])
{
while(height[left+1]<height[left] && left < right)
left++;
left++;
}
else
{
while(height[right-1]<height[right] && right > left)
right--;
right--;
}
}
return ans;
}