总结一下有关两个指针的算法题。这里的指针起游标的作用，一般用在处理字符串或者数组的相关问题上。有两个指针从头尾向中间移动，也有从头到尾一前一后一起移动。
1.求一个字符串的最大不重复子串的长度
一种接近暴力求解的方法就是遍历所有可能的子串组合，然后找出其中最长的一个。每次拿到一个子串的时候使用HashSet去判断有没有重复字符，如果有则不参与最长的比对计算。但是这种方式的时间复杂度太高，为O(n^3)。
代码如下：
public int lengthOfLongestSubstring(String s) {
//全局最大数
int max = 0;
for(int i = 0;i<s.length();i++){
// j比i先走一步，这里j如果小于s.length()的话，一个字符的时候不会进入循环
for(int j = i+1;j<=s.length();j++){
//判断子串没有重复字符的时候才进入
if(!hasRepeated(s.substring(i,j))){
max = Math.max(max,j-i);
}
}
}
return max;
}
public boolean hasRepeated(String substr){
HashSet<Character> set = new HashSet<Character>();
boolean flag = true;
for(Character c :substr.toCharArray()){
if(set.contains(c)){
flag = true;
break;
}else {
set.add(c);
flag = false;
}
}
return flag;
}
上述代码优化一下，还是使用两个游标。游标j先走，如果遇到的字符不重复则继续走，并求最大值；否则，后走的游标向前走一步。代码如下：
public int lengthOfLongestSubstring(String s) {
int i = 0,j = 0,max = 0;
ArrayList<Character> list = new ArrayList<Character>();
while(i<s.length() && j<s.length()){
if(list.contains(s.charAt(j))){
//如果直接写list.remove(s.charAt(i++)) 会执行remove(int index)方法导致数组越界异常
Character c = s.charAt(i++);
list.remove(c);
}else{
list.add(s.charAt(j++));
max = Math.max(j-i,max);
}
}
return max;
}
代码较为简洁，执行效率还不错，打败了85%的提交。
2.最大容器
给定一个整数数组array,再给定一个坐标轴，数组中第i个数对应坐标轴上的点为（i,array[i])。从坐标点a(i,array[i])向坐标点b(i,0)连一条垂直于x轴的竖线，另外从坐标点c(j,array[j])向坐标点d(j,0)连接另外一条垂直于x轴的竖线。两条连线组成一个桶，这个桶能装的水量取决于桶的短板。求所有坐标点可能形成的桶中能装最多水的桶面积。
对于两个坐标点a(i,array[i]),b(j,array[j])形成的面积为area = Math.min(array[i],array[j])*(j-i)。
和上题一样依然可以使用暴力求解的方式找出最大面积，但是时间复杂度太高。下面给出一种时间复杂度为O(N)的解法：
public int maxArea(int[] height) {
int l = 0,r = height.length-1,max=0;
while(l<r){
max = Math.max(max,Math.min(height[l],height[r])*(r-l));
if(height[l]<height[r]){
l++;
}else{
r--;
}
}
return max;
}