双指针算法学习总结以及实现案例

双指针算法简介：指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（左右指针）的指针进行扫描，从而达到相应的目的。换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

具体实现案例如下：

第一类：左右指针

  leetcode.125-验证回文串，全ac代码如下：

class Solution{//功能实现函数
public:
         bool isPalindrome(string s){
int start=0;i int end=s.size()-1;
while(start<end){
while(start<end&&!isalum(s[start]))//start位置如果是字母数字字符则向左移动
       start++;
while(start<end&&!isalnum(s[end]))//同理满足条件时end移动
       end--;
if(tolower(s[end])!=tolower(s[start]))//小写字母不同则返回false
   return false;
start++; end--;
}
return false;
  } 
};

 代码分析：回文是双指针算法中比较常见的一种类型，不难发现回文字符串是对称分布的，因此初始化两个移动速度相同的指针遍历字符串即可。

第二类：快慢指针

  （1）leetcode.19-删除链表的倒数第N个结点（比较明显的快慢指针）全ac代码如下：

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* l=new ListNode(0, head);//new一个数值为0的结点作为头结点
ListNode* fast=head; ListNode* slow=l; ListNode* ans;
for (int i=0;i<n;i++)
    fast=fast->next;//先移动快指针
while(fast){
slow=slow->next; fast=fast->next;//快指针不为空时，慢指针，快指针移动一个单位
}
slow->next=slow->next->next;
ans=l->next;
delete l;//删除new的头结点
return ans;
}
};

 代码分析：根据题意，要先找到链表的中间节点，再删除。因此不难想到双指针算法，初始化两个快慢指针，快指针先移动，然后每次都会比慢指针夺走一步，因此当快指针到结尾时慢指针指向位置正好是中间结点，delete掉然后slow指向slow->next->next即可。下图可以形象理解移动过程：

（2）leetcode.142-快乐数（不明显的快慢指针以及环型结构，做的时候一点也不快乐），全ac代码如下：

class Solution{
public:
       bool  isHappy(int n){
int fast=next(n);int slow=n;
while(fast!=slow&&fast!=1){
slow=next(slow); fast=next(next(fast));
}
return (fast==1);
}
public:
int next(int n){//写一个函数计算每一位数平方和
int x;
int sum=0;
while(n>0){
x=n%10;n=n/10;sum+=x*x;
      }
return sum;
   }
};

 代码分析：刚入手此题时其实想不到会成环。当仔细观察一个测试用例后会发现如果一个数每一位数的平方和无论是否会找不到1则会一直循环下去，因此成环，所以初始化两个快慢指针，如果存在1的话，快慢指针在一个环型结构中遍历总会相遇直到找到1或者快慢指针值相同。所以当fast和slow不相等且fast不是1时，因此分两种情况，一种是会一直走下去直到两个指针同时走到1，另外一种是由于快指针走得快所以当fast先到1时即可跳出循环，此时即为快乐数。