基础算法--双指针练习总结

Acwing部分练习:

799.最长连续不重复子序列

暴力 未AC(53 points):

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,a[N];
bool check(int l,int r){
    for(int i=l;i<=r;i++){
        for(int j=i;j<=r;j++){
            if(i!=j&&a[i]==a[j]){
                return false;
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(check(i,j)){
                ans=max(ans,j-i+1);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

快慢指针 优化(AC):

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,a[N],cnt[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1,j=1;i<=n;i++){
        cnt[a[i]]++;
        while(cnt[a[i]]>1){
            cnt[a[j]]--;
            j++;
        }
        ans=max(ans,i-j+1);
    }
    cout<<ans<<endl;
    return 0;
}

800.数组元素的目标和

暴力 未AC:

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,x,a[N],b[N];
int main(){
    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;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]+b[j]==x){
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
    return 0;
}

对撞指针 优化(AC):

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,x,a[N],b[N];
int main(){
    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(a[i]+b[j]==x){
            cout<<i<<" "<<j<<endl;
            return 0;
        }
    }
    return 0;
}

洛谷部分练习:

P1102 A-B 数对

暴力 未AC(76 points):

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
long long n,c,a[N],ans;
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]-a[j]==c){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

快慢指针 一个快指针,两个慢指针优化(AC):

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
long long n,c,a[N],ans;
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1,j=1,k=1;i<=n;i++){
        while(j<=i&&a[i]-a[j]>=c){
            j++;
        }
        while(k<=i&&a[i]-a[k]>c){
            k++;
        }
        ans+=j-k;
    }
    cout<<ans<<endl;
    return 0;
}

P8667 [蓝桥杯 2018 省 B] 递增三元组

 暴力 未AC(60 points):

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],c[N];
long long ans=0;
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(a[i]<b[j]&&b[j]<c[k]){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

 快慢指针 一个快指针,两个慢指针优化(AC):

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],c[N];
long long ans=0;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n);
    for(int i=0;i<n;i++) cin>>b[i]; sort(b,b+n);
    for(int i=0;i<n;i++) cin>>c[i]; sort(c,c+n,cmp);
    for(int i=0,j=0,k=n-1;j<n;j++){
        while(i<n&&a[i]<b[j]){
            i++;
        }
        while(k>=0&&c[k]<=b[j]){
            k--;
        }
        ans+=(long long)i*(k+1);
    }
    cout<<ans<<endl;
    return 0;
}

P3143 [USACO16OPEN] Diamond Collector S

 快慢指针 前后分别遍历(AC):

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+5;
int n,k,a[N];
long long l[N],r[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1,j=1;i<=n;i++){
        while(j<=i&&a[i]-a[j]>k){
            j++;
        }
        l[i]=max(l[i-1],(long long)i-j+1);
    }
    for(int i=n,j=n;i>=1;i--){
        while(j>=i&&a[j]-a[i]>k){
            j--;
        }
        r[i]=max(r[i-1],(long long)j-i+1);
    }
    long long ans=0;
    for(int i=1;i<=n-1;i++) ans=max(ans,l[i]+r[i+1]);
    cout<<ans<<endl;
    return 0;
}