算法——双指针

前言

双指针算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解递推。

一、什么是双指针

双指针算法涉及使用两个指针（索引或引用），通常分别称为“快指针”和“慢指针”或“左指针”和“右指针”，以协同进行遍历或搜索。该算法的核心思想是通过移动这两个指针来实现特定的目标，例如寻找一对元素的和、判断是否存在某种关系或在特定条件下移动其中一个指针。

二、算法特点

时间复杂度低：
双指针算法通常能够在O(n)的时间复杂度内解决问题，相较于暴力搜索的O(n^2)时间复杂度，具有显著的优势。
这是因为双指针算法通过同时操作两个指针，减少了重复计算和遍历次数。

空间复杂度低：
双指针算法通常只需要常数级别的额外空间，即O(1)的空间复杂度。这使得双指针算法在处理大规模数据时更加高效，因为它不需要额外的存储空间来存储中间结果。

适用性强：
双指针算法可以应用于多种数据结构，如数组、链表等。
它还可以用于解决多种类型的问题，如查找和排序、判断链表是否有环、计算最大子数组和等。

三、算法实现步骤

1.初始化指针：根据问题的具体需求，选择合适的初始位置来初始化指针。

2.遍历数据结构：使用循环遍历数据结构，同时操作两个指针。

3.判断条件：在遍历过程中，根据当前指针位置和目标条件来判断是否满足要求。

4.移动指针：根据判断结果，移动指针以继续搜索或缩小搜索范围。

5.记录结果：当找到满足条件的解时，记录结果并继续搜索，直到遍历完整个数据结构。

四、常见形式

对撞指针：两个指针分别从线性数据结构的两端向中间移动，常用于查找和排序问题。例如，在有序数组中查找和为特定值的两个数，可以使用一个头指针和一个尾指针，分别指向数组的最左边和最右边，通过比较两个指针指向的值与目标值的大小关系，移动指针来缩小搜索范围。

快慢指针：一个指针移动速度较快，另一个移动速度较慢。这常用于解决链表中的问题，如判断链表是否有环、找到链表的中间节点等。快慢指针相遇时，可以判断链表是否有环，并通过调整指针位置找到环的起点。

滑动窗口：使用两个指针维护一个窗口，通过移动窗口的左右边界解决问题。这类问题常见于字符串和数组处理，例如找到最短的包含所有字符的子串或计算数组中的最大子数组和等。

同向双指针：两个指针方向相同，通过控制其中一个指针的位置来处理问题。例如，在一个有序数组中查找两个数，使它们的和等于给定值。

五、应用场景与示例

移动零：使用双指针将数组中的零移动到末尾，同时保持非零元素的相对顺序。

复写零：在原数组上复写零，即每遇到一个零，就在其后面再添加一个零，同时保证不覆盖后面的数字。

快乐数：判断一个数是否为快乐数。快乐数定义为：一个正整数，每一次将该数替换为其每个位置上的数字的平方和，然后重复这个过程，直到这个数变为1，也可能是无限循环但始终变不到1。可以使用快慢指针的思想来判断是否存在循环。

盛最多水的容器：给定一个整数数组，其中每个元素代表一个垂直线条的高度，找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。可以使用双指针从两端向中间遍历，通过比较高度移动指针来找到最大面积。

有效三角形的个数：给定一个包含非负整数的数组，判断其中可以组成三角形的三个数的个数。可以先对数组进行排序，然后使用双指针来判断任意三个数是否能组成三角形。

三数之和：给定一个包含n个整数的数组，判断该数组中是否存在三个元素a，b，c，使得a+b+c=0？找出所有满足条件且不重复的三元组。可以使用双指针在排序后的数组中遍历并查找满足条件的三元组。

六、优势与注意事项

双指针算法通常能够在O(n)的时间复杂度内解决问题，具有较好的效率。然而，在使用双指针算法时需要注意以下几点：

初始化指针位置：根据问题的具体需求，选择合适的初始位置来初始化指针。

控制指针移动：根据当前指针位置和目标条件来决定如何移动指针。

避免重复计算：在移动指针时，要注意避免重复计算已经处理过的元素。

处理边界情况：对于数组为空或仅有一个元素等边界情况，需要进行特殊处理。

七、双指针算法动态图解

八、经典例题

1. 回文判定

代码题解

#include <iostream>
#include<string>
using namespace std;
string s;
int main()
{
    cin>>s;
    int l=0,r=s.size()-1;
    while(l<r){
        if(s[l]==s[r])
            l++,r--;
        else {
            cout<<"N"<<endl;
            break;
        }
    }
    if(l>=r)cout<<"Y"<<endl;
    return 0;
}

2. 反转字符串中的字符

代码题解

#include <iostream>
#include<cstring>
using namespace std;
int main()
{
    char s[1000];
    cin.getline(s,101,'\n');
    int l=0;int r=strlen(s)-1;
    while(l<r){
        swap(s[l],s[r]);
        l++,r--;
    }
    cout<<s<<endl;
    return 0;
}

3.等腰三角

代码题解

#include <iostream>
#include<algorithm>
using namespace std;

#define maxn 200001
int A[maxn],B[maxn],C[maxn];
//  1 2 3 4     A
//  2 4 6 8     C
//  2 2 3 4     B
//  i
//  j
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>A[i];
        C[i]=2*A[i];
    }
    for(int i=0;i<n;i++){
        cin>>B[i];
    }
    sort(C,C+n);//对c数组进行递增排序
    sort(B,B+n);//与c数组同理
    int i=0,j=0,ans=0;
    while(i<n&&j<n){
        if(C[i]>B[j])j++,ans++;//两个数组排好序之后，如b[j]>=c[i],那么也就是说j以后的b数组所有数都比c[i]大，i++
        i++;
    }
    cout<<ans<<endl;
    return 0;
}

结语

学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，不会的地方就问，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。

关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家。