双指针算法 Two Pointers

 双指针算法可以归类为：

• 普通双指针：两个指针往同一个方向移动
• 对撞双指针：两个指针面对面移动
• 快慢双指针：一个快指针+一个慢指针

例题：从已经排序好的数组 a中找出相加等于n的两项

1. 解法1：两个指针ij从前往后遍历，将每一次遍历组合都与n进行比较，时间复杂度是O(n2)
2. 解法2：由于数组有序，可以使用对撞双指针，将ij分别设置在数组头尾面对面移动，当n大于ij所指元素的和时，i向后移动，当n小于ij所指元素的和时，j向前移动，直至i与j相遇

#include<stdio.h>
void find_sum_1(int *a,int len,int sum)
//解法一：暴力解法
{
for(int i=0;i<len-1;i++)
{
for(int j=i+1;j<len;j++)
{
if(a[i]+a[j]==sum)
printf("%d %dn",a[i],a[j]);
}
}
}
void find_sum_2(int *a,int len,int sum)
//解法二：对撞双指针
{
int i=0,j=len-1;
while(i!=j)
{
if(a[i]+a[j]==sum)
{
printf("%d %dn",a[i],a[j]);
i++;
}
else if(a[i]+a[j]<sum)
++i;
else if(a[i]+a[j]>sum)
--j;
}
}
int main()
{
int a[]={1,3,5,6,8,10,12,22};
int len=8;
int sum=15;
find_sum_2(a,len,sum);
}

• 当出现“有序”条件时，可以考虑使用对撞指针
• 检测是否是环形链表时，可以用到快慢双指针：设置一个每次后移一步的指针i和一个每次后移两步的指针j，如果是环形链表，则i和j终将相遇

相关习题：

141.环形链表          简单

力扣

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

• 链表中节点的数目范围是 [0, 104]

如果链表中存在环 ，则返回 true 。 否则，返回 false

思路：判断环形链表，使用快慢双指针，当快指针追上慢指针时说明存在环形

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head)
{
    int i=0;
    struct ListNode *ptr1=head,*ptr2=head;
    if(head==NULL)
        return false;
    while(i<10000)
   {
       ++i;
        if(ptr2->next!=NULL&&ptr2->next->next!=NULL)
            ptr2=ptr2->next->next;
//快指针
        else
            return false;
        ptr1=ptr1->next;
//慢指针
        if(ptr2==ptr1)
            return true;
   }
    return false;
}

881.救生艇          中等

力扣

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

思路：使用对撞双指针，同时考虑最重和最轻的人，如果最重的人无法负载则一人一艘船，最轻最重加起来可以负载则一艘船；开始时要对数组进行排序，使用快速排序

void swap(int *a, int *b)   
{ 
    int temp;  
   temp = *a;  
   *a = *b;  
   *b = temp;  
}
void QuickSort(int *arr, int maxlen, int begin, int end) 
{ 
    int i, j;  
    if (begin < end) {  
        i = begin + 1; 
       j = end;        
        while (i<j) 
       {  
            if(arr[i]>arr[begin])
           {  
                swap(&arr[i],&arr[j]);
               --j;  
           } 
            else  
               ++i; 
       }  
        if (arr[i]>=arr[begin])
           --i;  
        swap(&arr[begin], &arr[i]);     
        QuickSort(arr,maxlen,begin,i); 
        QuickSort(arr,maxlen,j,end); 
   }  
}   
int numRescueBoats(int* people, int peopleSize, int limit)
{
    QuickSort(people,peopleSize,0,peopleSize-1);
    int i=0,j=peopleSize-1;
    int res=0;      //结果船数
    int count=0;    //已经上船的人数
    while(i<j)
   {
        if(people[j]+people[i]<=limit)      //可以装下
       {
           ++res;
           ++i;
           --j;
            count+=2;
       }
        else if(people[j]+people[i]>limit)  //最重的和最轻的在一起无法承载，最重的只能自己一艘船
       {
           ++res;
           --j;
           ++count;
       }
   }
    if(count!=peopleSize)
       ++res;
    return res;
}

最后

以上就是凶狠毛豆为你收集整理的双指针算法 Two Pointers的全部内容，希望文章能够帮你解决双指针算法 Two Pointers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。