求总和能被 3 整除的最长序列长度
Find the longest sequence length whose sum is divisible by 3
我有一个需要用 O(n) 时间复杂度完成的练习，但是，我只能用 O(n^2) 的解决方案来解决它。
你有一个数组，你需要计算最长的连续序列，这样它的和可以除以 3 没有任何余数。例如对于array {1,2,3,-4,-1)，函数将return 4 因为它的sum(0) 可以划分为3 的最长序列是{2,3,-4,-1}.
我的解决方案 O(n^2) 基于 arithmetic progression。有什么办法可以做到 O(n) 的复杂度吗？
拜托，我只想要一个线索或理论上的解释。请不要写完整的解决方案:)
我们来看看前缀和。当且仅当
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3 时，[L, R] 子数组才能被 3 整除。这个观察给出了一个非常简单的线性解（因为前缀和只有3个可能的值mod3，我们可以简单地找到第一个和最后一个）。
例如输入数组为{1, 2, 3, -4, -1}，则前缀和为{0, 1, 0, 0, 2, 1}。 （因为前缀为空，所以有 n + 1 个前缀和）。现在您可以只看一下 0、1 和 2 的第一次和最后一次出现。
作为一个非CS人士，这很有趣。我的第一种方法是简单地计算 运行 总和 mod 3。您将得到 {0,1,2} 的序列。现在找第一个和最后一个0，第一个和最后一个1，第一个和最后一个2，比较它们各自的距离...
你应用了动态规划。
对于每个位置，您计算 3 个值：
- 以和 s = 0 的位置结束的最长序列 mod 3
- 以和 s = 1 的位置结束的最长序列 mod 3
- 以和 s = 2 的位置结束的最长序列 mod 3
因此给定位置 i 的这个值，您可以轻松计算位置 i+1 的新值。
遍历数组，边走边求和。记录第一个取模和为0的位置。另外，记录模和为1的第一个位置。最后，记录模和为2.
的第一个位置
也向后做同样的事情，记录模和为0、1和2的最后位置。这为最长序列提供了三种可能性 - 您只需检查哪对相距最远。
我有一个需要用 O(n) 时间复杂度完成的练习，但是，我只能用 O(n^2) 的解决方案来解决它。
你有一个数组，你需要计算最长的连续序列，这样它的和可以除以 3 没有任何余数。例如对于array {1,2,3,-4,-1)，函数将return 4 因为它的sum(0) 可以划分为3 的最长序列是{2,3,-4,-1}.
我的解决方案 O(n^2) 基于 arithmetic progression。有什么办法可以做到 O(n) 的复杂度吗？
拜托，我只想要一个线索或理论上的解释。请不要写完整的解决方案:)
我们来看看前缀和。当且仅当 prefixSum[L - 1] mod 3 = prefixSum[R] mod 3 时，[L, R] 子数组才能被 3 整除。这个观察给出了一个非常简单的线性解（因为前缀和只有3个可能的值mod3，我们可以简单地找到第一个和最后一个）。
例如输入数组为{1, 2, 3, -4, -1}，则前缀和为{0, 1, 0, 0, 2, 1}。 （因为前缀为空，所以有 n + 1 个前缀和）。现在您可以只看一下 0、1 和 2 的第一次和最后一次出现。
作为一个非CS人士，这很有趣。我的第一种方法是简单地计算 运行 总和 mod 3。您将得到 {0,1,2} 的序列。现在找第一个和最后一个0，第一个和最后一个1，第一个和最后一个2，比较它们各自的距离...
你应用了动态规划。 对于每个位置，您计算 3 个值：
- 以和 s = 0 的位置结束的最长序列 mod 3
- 以和 s = 1 的位置结束的最长序列 mod 3
- 以和 s = 2 的位置结束的最长序列 mod 3
因此给定位置 i 的这个值，您可以轻松计算位置 i+1 的新值。
遍历数组，边走边求和。记录第一个取模和为0的位置。另外，记录模和为1的第一个位置。最后，记录模和为2.
也向后做同样的事情，记录模和为0、1和2的最后位置。这为最长序列提供了三种可能性 - 您只需检查哪对相距最远。