双指针算法 | OI笔记

双指针算法

核心思想：

对于

for (int i = 0; i < n; ;i ++)
    for (int j = 0; j < n; j ++)

一个O(n^2^)时间复杂度的爆搜算法，使用

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

优化为O(n)级别的算法
为什么是O(n)呢？

因为j不会在每个i循环内更新成0，再开始循环，而是直接沿用上次循环的j值，因而j移动的次数总共是< n 的，而i = 0; i < 0; i ++移动次数也是小于n的，所以双指针算法总共的时间复杂度是O(n)的

例题：acwing799-最长连续不重复子序列

#include <iostream>

using namespace std;

const int N = 100000;
int a[N + 10];
int s[N + 10];

int main()
{
	int n;
	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]] --;
			j ++;
		}
		res = max(res, i - j + 1);
	}
	
	cout << res << endl;
	return 0;
}