核心思路

首先打一个 O ( n 2 ) O(n^2) O(n2)的暴力，然后考虑性质；

当i,j具有单调性的时候，那么我们才可以用双指针来优化；

基础例题

最长连续不重复子序列

传送门

题面

思路

我们用 r r r表示右指针， l l l表示左指针；

假设r向右移动的时候，l向左移动才是最优解；

我们维护[l,r]表示当前的最长不重复的子段，那么当l向左移动才是最优解，那么就说明我们之前l指针向右移动是非法的；

也就是说我们可以用向左移动的l替换掉当前的l，使得答案最优，那么就是不移动的情况；

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int a[N],s[N];
void solve(){
	int n;
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> a[i];
	}
	int l = 1,ans = 0;
	for(int r=1;r<=n;++r){
		++s[a[r]];
		while(l<=r && s[a[r]] > 1){
			--s[a[l]];
			++l;
		}
		ans = max(ans,r-l+1);
	}
	cout << ans;
}

signed main(){
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

数组元素的目标和

传送门

题面

思路

见注释

Code

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N],b[N];

int main(){
    int n,m,x;
    cin >> n >> m >> x;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=m;++i) cin >> b[i];
    int j = m;
    //因为数组都是单调上升的
    //那么a(i) + b(j) > x 当i往右移动的时候 那么j必然左移
    //因此是具有单调性的
    for(int i=1;i<=n;++i){
        while(j>=1 && a[i]+b[j] > x) --j;
        if(a[i] + b[j] == x){
            //下标从0开始
            cout << (i-1) << ' ' << (j-1) << '\n';
            break;
        }
    }
    return 0;
}

进阶例题

见其中的统计子矩阵