双指针

思路

双指针算法在于优化，当发现时间复杂度过高时可以考虑双指针优化

要求：

• 变化单调 即遍历时，一个边界往某个方向变化，另一个边界只往一个方向变化，而不是自由变化。

例如：当右边界逐渐靠右，假设范围大小有限制，随着右边不断变大，发现左右边界的范围超过要求的范围了，左边界只能向右移动来满足要求，这样就是单调变化。

实现

int l = 0, r = 0;
for(r = 0; r < n; r ++)
{
	//statement
	while(r - l > k)
	{
		l ++;
	}
	//statement
}

这样将原本可以两维变化（左右都动）的问题简化为一维，优化时间复杂度

具体例子

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