当前位置：首页 > article >正文

双指针算法（快慢指针/对撞指针法）

article 2025/4/1 14:03:52

一、27. 移除元素 - 力扣（LeetCode）

二、双指针算法📌

三、其他题目（见得题多了，一眼就知道用双指针优化）

（1）替换数字 -卡玛网（不用额外的辅助空间）

（2）空格分割字符串

（3）AcWing 799. 最长连续不重复子序列 - AcWing 【滑动窗口】

（4）800. 数组元素的目标和 - AcWing==

（5）2816. 判断子序列

一、27. 移除元素 - 力扣（LeetCode）

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖 ，这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素，第二个for循环更新数组。

二、双指针算法📌

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。最常见的双指针算法有两种：一种是，在一个序列里边，用两个指针维护一段区间；另一种是，在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序。双指针算法的核心思想（作用）：优化 -----双指针算法-CSDN博客

定义快慢指针

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。

先看下本题代码：（本题简单的不形）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.size();fast++)
        {
            if(nums[fast]!=val) 
                nums[slow++]=nums[fast];
        }
        return slow;
        
    }
};

三、其他题目（见得题多了，一眼就知道用双指针优化）

（1）替换数字 -卡玛网（不用额外的辅助空间）

https://kamacoder.com/problempage.php?pid=1064

有点is ，挺有趣的一道题目 数组填充类的问题，先预先给数组扩容带填充后的大小，然后在从后向前进行操作；

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int cnt=0;//统计数字的个数
    for(int i=0;i<s.length();i++) 
    {
        if(s[i]>='0'&&s[i]<='9') cnt++;
    }
    //扩容:扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
    int fast = s.length() - 1;  // 原始字符串的最后一个字符
    s.resize(s.size()+cnt*5);
    //从后往前替换
    int slow=s.size()-1;
    for(;fast>=0;fast--)
    {
        if(s[fast]>='0'&&s[fast]<='9')//替换
        {
            s[slow--]='r';
            s[slow--]='e';
            s[slow--]='b';
            s[slow--]='m';
            s[slow--]='u';
            s[slow--]='n';
        }
        else //不是数字
            s[slow--]=s[fast];
    }

    cout<<s;
return 0;
}

（2）空格分割字符串

int main() {
    string str;
    getline(cin, str);
    
    for (int slow = 0; slow < str.size(); slow++) {
        int fast = slow;
        // 找到第一个空格或到达字符串末尾
        while (fast < str.size() && str[fast] != ' ') {
            fast++;
        }

        // 输出当前单词的每个字符
        for (int k = slow; k < fast; k++) {
            cout << str[k] << endl;
        }
        // 更新 slow 跳到下一个单词的开始位置
        slow = fast;
     
    }

    return 0;
}

（3）AcWing 799. 最长连续不重复子序列 - AcWing 【滑动窗口】

滑动窗口算法：使用两个指针（slow 和 fast）来控制窗口的左右边界 AcWing 154. 滑动窗口-CSDN博客（之前刷过的一道滑动窗口的题）

初始化两个指针：slow 和 fast，都从数组的开始位置出发。

fast 指针逐渐向右扩展窗口，将当前元素 a[fast] 加入到窗口中，并记录该元素的出现次数。

如果当前元素重复（即 a[fast] 在窗口中已经出现过），则移动 slow 指针，直到窗口内没有重复元素。每移动一次 slow，就减少其对应元素的计数。

在每一步，计算窗口的大小（即 fast - slow + 1），并更新结果 res，保持记录最大长度的值。

题目还是比较难想的········

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];

int main() {
    int n;
    int res = 0;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];
    // 滑动窗口
    for (int slow = 0, fast = 0; fast < n; fast++) {
        s[a[fast]]++;  // 记录当前元素的出现次数
        // 当出现重复元素时，移动slow指针
        while (s[a[fast]] >1) {  // 重复元素出现
            s[a[slow]]--;  // 减少当前slow指针位置的元素计数
            slow++;  // 移动slow指针，直到没有重复元素
        }
        // 计算当前窗口的长度，更新结果
        res = max(res, fast - slow + 1);
    }
    cout << res << endl;
    return 0;
}

（4）800. 数组元素的目标和 - AcWing==

挺简单的，巧妙用到升序排列的条件

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    //在B数组中找等于x-a的tar
    //升序排序的，所以j 从数组 b[] 的尾部开始往前移动（即递减），
        //如果 a[i] + b[j] > x，则继续移动 j，直到a[i] + b[j] == x
    //指针1遍历A数组，指针2在B数组中找
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0,j=m-1;i<n;i++)
    {
        while(j>=0&&a[i]+b[j]>x) j--;
        if(j>=0&&a[i]+b[j]==x) cout<<i<<" "<<j;
        
    }
    return 0;
}

（5）2816. 判断子序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
// a是b的子序列嘛？
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    int j=0;//用于在a数组上移动
    for(int i=0;i<m;i++) //遍历b
    {
        
        if(j<n&&b[i]==a[j]) // 找到一个
        {
            j++; // 找下一个
            //cout<<j;
          
        }
    }
    if(j==n) cout<<"Yes"; //全都找到了
    else cout<<"No";
    return 0;
}