algorithm - 求总和能被 3 整除的最长序列长度

Question

我有一个需要以 O(n) 时间复杂度完成的练习，但是，我只能用 O(n^2) 的解决方案来解决它。

你有一个数组，你需要计算最长的连续序列，这样它的总和就可以除以 3，没有余数。例如对于array {1,2,3,-4,-1)，函数将返回4，因为它的sum(0)可以被分割的最长序列3 是 {2,3,-4,-1}。

我的解决方案 O(n^2) 基于算术级数。有什么办法可以做到 O(n) 的复杂度吗？

拜托，我只想要一个线索或理论上的解释。请不要写完整的解决方案:)

Answer 1

让我们来看看前缀和。当且仅当
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3 时，[L, R] 子数组才能被 3 整除。这个观察给出了一个非常简单的线性解决方案(因为前缀和模 3 只有 3 个可能的值，我们可以简单地找到第一个和最后一个)。

例如，如果输入数组为{1, 2, 3, -4, -1}，则前缀和为{0, 1, 0, 0, 2, 1}。 (因为前缀为空，所以有 n + 1 个前缀和)。现在您可以只看一下 0、1 和 2 的第一次和最后一次出现。