Section 6.双指针

Section 6.双指针

核心思想：

对于一个序列：用两个指针维护一段区间对于两个序列：用两个指针对两个序列进行有规律地维护（如归并排序）

将时间复杂度O(n^2)的算法优化至O(n)

for (int i = 0; i < n; i++)
{
	for (int j = 0; i < m; j++)
	{
		//...
	}
}

将朴素变得高雅（

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

配套练习

Acwing799https://www.acwing.com/problem/content/801/Acwing800https://www.acwing.com/problem/content/802/Acwing2816https://www.acwing.com/problem/content/2818/