双指针算法

思想

双指针算法都是把暴力算法写出来，然后看有没有单调性，如果有单调性就可以把时间复杂度降低
两个指针移动将O(n ^ 2)的算法优化成O(n)   

特点

*模板

```
    for (int i = 0; i < n; i++)
        while (i < j && check(i, j)) j ++;
```    

// 找出连续数字最长的长度
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int a[N], s[N];

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++)
    {
        s[a[i]] ++;
        while (s[a[i]] > 1)
        {
            s[a[j]] -- ;  //关键一步 将记录在s数组中的数字弹出，这样就可以往后遍历的时候，在遇到相同的数字不至于被算作重复的。
            j ++;
        }
        
        res = max(res, i - j + 1);
    }
    
    cout << res << endl;
    
    return 0;
}

双指针算法

思想

特点

FEATURED TAGS