找到最长的序列长度的总和被3整除 [英] Find the longest sequence length whose sum is divisible by 3

问题描述

我有一个运动需要被带O完成（n）的时间复杂度，但是，我只能解决它为O（n ^ 2）解决方案。

I have an exercise that needs to be done with O(n) time complexity, however, I can only solve it with an O(n^2) solution.

您有一个数组，你需要计算时间最长的连续序列，它的款项可分为3没有任何剩余。例如，对于数组{1,2,3，-4，-1），该函数将返回4，因为最长的序列，其 SUM（ 0）可分为 3 是 {2,3，-4，-1} 。

You have an array and you need to count the longest contiguous sequence such that it's sum can be divided to 3 without any remainder. For example for array {1,2,3,-4,-1), the function will return 4 because the longest sequence that its sum(0) can be divided to 3 is {2,3,-4,-1}.

我的解决方案为O（n ^ 2）是基于 算术级数 。有没有什么办法来为O（n）的复杂性做呢？

My solution O(n^2) is based on arithmetic progression. Is there any way to do it with O(n) complexity?

请，我只想要一个线索或理论解释。请不要写了完整的解决方案：）

Please, I only want a clue or a theoretical explanation. Please don't write the full solution :)

推荐答案

让我们来看看preFIX款项。 A [L，R] 子阵列divisble 3当且仅当
prefixSum [L - 1模3 = prefixSum [R]模3 。该观察结果给出了一个非常简单的线性溶液（因为有一个preFIX总和模3的仅3个可能的值，我们可以简单地找到第一个和最后一个）。

Let's take a look at prefix sums. A [L, R] subarray is divisble by 3 if and only if
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3. This observation gives a very simple linear solution(because there are only 3 possible values of a prefix sum mod 3, we can simply find the first and the last one).

例如，如果输入数组是{1，2，3，-4，-1}的preFIX和数是{0，1，0，0，2，1}。 （有n + 1 preFIX款项，因为一个空的preFIX）。现在，你可以看看的0，1和2的首次和最后出现。

For example, if the input array is {1, 2, 3, -4, -1}, the prefix sums are {0, 1, 0, 0, 2, 1}. (there are n + 1 prefix sums because of an empty prefix). Now you can just take a look at the first and last occurrence of 0, 1 and 2.

这篇关于找到最长的序列长度的总和被3整除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！