双指针算法

定义了两个指针l,r，用这两个指针来遍历一个数组，那么最多每个指针走一遍数组，所以复杂度是 2N，这比纯暴力两个循环遍历数组 N²要好很多

双指针算法的核心思想就是运用某些性质将朴素暴力算法优化到 O(N)

具体解题的时候可以先自己想一下暴力怎么解，然后看看我们枚举的时候 ij 有没有什么单调关系，然后利用单调关系来尝试双指针优化

背景：

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

y 总的写法

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

//q是原数组，s用来记录区间内元素的数量，注意这两个N不是一个意思
//第一个是数组的长度，第二个是数组元素的范围
int q[N], s[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];

    int res = 0;
    //维护一个区间
    for(int i = 0, j = 0; i < n; i++)
    {
        s[q[i]]++;//向右扩展区间右端点
        //当扩展完区间右端点之后，有可能这个元素q[i]会有重复，下面这个while循环就是用来去除重复
        //去重只有一个办法，就是收缩区间左端点，同时收缩时要保证j是小于i的
        while(j < i && s[q[i]]>1) s[q[j++]] --;//区间数量减一，之后区间断点右移
        //完成上述扩展和收缩之后，该区间是一个满足要求的区间，记录一下长度
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}

我的两种写法，分别是从左边开始扫的和从右边开始扫的双指针

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;


int main()
{
    cin >> n;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++) cin >> arr[i];

    vector<int> cnt(100010,0);
    int ans=0;
    int r=0;

    for(int l=0;l<n;l++)
    {
        while(r < n && cnt[arr[r]] == 0) // 这个循环会一直找到对于当前l能有的最大的r 一旦这个r指向的元素不满足就会停止
        {
            cnt[arr[r++]]++;
        }
        ans = max(ans,r-l);  //停下的时候r是第一个不满足的，所以这里应该是r-l+1 -1 表示当前的r不能算进这个长度

        cnt[arr[l]]--;  //因为这个l已经开始容不下r了，所以把cnt中这个l移出去，循环往下进行也会让l++
        // 如果新的循环的l还是容不下r，那就说明这个l对应的最长长度要小于上一个循环计算得到的ans，由于r没有再向右移动
        // 这个循环里ans取到的max值一定是上一个循环的，这样的情况会一直持续到r开始增长，甚至于是r增长到r-l足够大
    }

    cout << ans;

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin >> arr[i];

    vector<int> cnt(100010,0); //用来辅助判断当前窗口情况是否满足不重复的条件 因为重复的话对应cnt会>1
    int l = n - 1;
    int ans =0;

    for(int r = n-1; r>=0;r--)  //在每次循环中都找到以r为右端点的最长的[l+1,r]满足题目条件
    {
        while(l>=0 && cnt[arr[l]] == 0)  //当前窗口能容下这个l
        {
            cnt[arr[l--]]++; //把这个l放进来
        }
        ans = max(ans,r-l);  //上面的循环结束的时候l会位于第一个不满足的，所以这里ans不能把这个l也算进来而是少算一个

        //现在要进行下一轮循环去找以r-1为右端点的，也就是这里要去掉r
        cnt[arr[r]]--;
        //为什么只去掉r不再去掉其它的呢？
        //因为上面的while已经保证[l+1,r]一定满足，我们在进入下轮循环的时候只动了r而没有动l，把r往左动那[l+1,r-1]还是
        //一定满足，所以不需要再去掉其它的。本质上来说就是cnt已经放进去的是不去掉r都valid的，现在我们已经解决了以r为
        //右端点的现在要解决以r-1为右端点的了，所以cnt里的arr对应的[l+1,r-1]更是全部合理，我们只需要在新的循环里判断
        //l是否能合理，以及它能合理以后l又能到达最左边的哪里，如果它还是不合理那这个while就会不执行，那得到的r-l会比
        //比上一个小1，不会是ans的候选项，也就是说，虽然我们在这个循环中没有得到以r-1为右端点的最大不重复序列，但是
        //这不重要了，我们不需要了
    }
    cout << ans;
    return 0;
}

背景

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n,m,x;
    cin >> n >> m >> x;
    
    vector<int> A(n);
    vector<int> B(m);
    for(int i=0;i<n;i++) cin >> A[i];
    for(int i=0;i<m;i++) cin >>B[i];
    
    int r=m-1;
    int l=0;
    
    for(l=0;l<n;l++)
    {
        while(r >= 0 && A[l]+B[r]>x) r--; //找到第一个r的位置使得 A[l]+B[r]<=x 然后如果是等于的话会被下面break
        // 如果是小于的话说明需要A那边的l去努力，这边已经尽力了
        if(A[l]+B[r] == x) break;
    }
    
    cout << l <<" " << r;
    
    return 0;
}