简介
双指针算法其实也可以称作是滑动窗口法，跟上一篇介绍的最长回文子串的介绍很相似，都是用两个指针来表示指针中间的区域，然后来计算区域中的数值或者是算一定的面积等。首先起始最原始是在链表里面，最简单的一个应用是判断链表是否有环，即用快慢指针来结合判断，
structure ListNode{
int val;
node *next;
};
ListNode * head = (ListNode*)malloc(sizeof(ListNode));
boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
这只是一个简单的应用，起始双指针在字符串里面由很广泛的应用，上一篇，最长的回文子串、最大子序列等，都是可以用双指针的方法来做的。双指针的主要思路如下所示，主要分为两个步骤
- 确定左右指针的移动范围
- 确定左右指针的移动方式[是一边移动完另一边再移动，还是两边一起动，还是有什么转移条件/触发条件]
在一定程度上，如果两个循环移动的话，效率比较低，时间复杂度为O(n^2),起始就是暴力破解的方法，在一定程度上是不推荐的。但是在字符床的处理的过程中还是比较常用的，主要是利用position 结合字符串的提取函数，substr(stat, len),来提取目标字符串。
下面以一个简单的例子来说明一下
水桶的最大盛水面积(Leetcode 11)
题目的描述主要就是找出木板里面盛水最多的区域，就是找出最大的面积。
代码如下：
int maxArea(vector<int>& height) {
int len=height.size();
int left=0,res=0,right=len-1;
while(left<len&&right>0){
int area=(right-left)*min(height[right],height[left]);
if(res<area)
res=area;
if(height[right]<height[left])//判断左右指针移动的顺序，移动的是移动小的那边，这个地方实现判断
right--;
else
left++;
}
return res;
}
