双指针算法总结

简介

双指针算法其实也可以称作是滑动窗口法，跟上一篇介绍的最长回文子串的介绍很相似，都是用两个指针来表示指针中间的区域，然后来计算区域中的数值或者是算一定的面积等。首先起始最原始是在链表里面，最简单的一个应用是判断链表是否有环，即用快慢指针来结合判断，

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;
}