求哈希做法的时间复杂度分析
查看原帖
求哈希做法的时间复杂度分析
554746
yiming564楼主2024/10/15 16:40

这篇题解 为例,其枚举区间的过程大致是:

for (int i = 1, l = 1; i <= n; i++)
{
	if (a[i] == 1) l = 1;
	chkmax(l, a[i]);
	if (i - l + 1 < 1) continue;
	ans += diff(i - l + 1, i) == sum[l];
}
for (int i = n, l = 1; i; i--)
{
	if (a[i] == 1) { l = 1; continue; }
	chkmax(l, a[i]);
	if (i + l - 1 > n) continue;
	ans += diff(i, i + l - 1) == sum[l];
}

我想知道这种枚举区间的方法的时间复杂度,但我不会分析。

2024/10/15 16:40
加载中...