我有一个需要用O（n）时间复杂度完成的练习，但是，我只能用O（n ^ 2）解决方案来解决它。
您有一个数组，需要对最长的连续序列进行计数，以便可以将其总和除以3而没有任何余数。例如array {1,2,3,-4,-1)，该函数将返回4，因为其sum(0)可以划分的最长序列3为{2,3,-4,-1}。
array {1,2,3,-4,-1)
sum(0)
3
{2,3,-4,-1}
我的解决方案O（n ^ 2）基于 arithmetic progression 。有没有办法做到O（n）的复杂性？
arithmetic progression
拜托，我只想要一个线索或理论上的解释。请不要写完整的解决方案:)
让我们看一下前缀和。一个[L, R]子阵列由3当且仅当divisble prefixSum[L - 1] mod 3 = prefixSum[R] mod 3。这个观察给出了一个非常简单的线性解（因为前缀和mod 3只有3个可能的值，我们可以简单地找到第一个和最后一个）。
[L, R]
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3
例如，如果输入数组为{1、2、3，-4，-1}，则前缀和为{0、1、0、0、2、1}。（由于前缀为空，所以存在n +1个前缀和）。现在，您只需看一下第一个和最后一个出现的0、1和2。
