解题思路

双指针用法
核心思想:优化(找单调性) 将暴力做法O(n²)优化到O(n)

样例

AcWing 800. 数组元素的目标和

算法1

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N];   //a[]表示原来的数, b[]表示区间[j,i]中每个数出现的次数

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

    int res = 0;   //计数

    for(int i = 0, j = 0; i < n; i ++ )
    {
        b[a[i]] ++ ;
        while(b[a[i]] > 1)
        {
            b[a[j]] -- ;
            j ++ ;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}