Section 6.双指针

• 核心思想：

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

• 将时间复杂度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++;
	//...
}

• 配套练习

Acwing799

Acwing800

Acwing2816

​