Section 6.双指针

Section 6.双指针,第1张

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/

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702863.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存