Jey*_*eyJ 17 algorithm math recursion time-complexity
我有一个需要用O(n)时间复杂度完成的练习,但是,我只能用O(n ^ 2)解决方案解决它.
你有一个数组,你需要计算最长的连续序列,使得它的总和可以被分成3而没有任何余数.例如array {1,2,3,-4,-1),函数将返回4,因为它sum(0)可以被分成的最长序列3是{2,3,-4,-1}.
我的解决方案O(n ^ 2)基于arithmetic progression.有没有办法用O(n)复杂度做到这一点？
拜托,我只想要一个线索或理论解释.请不要写完整的解决方案:)
kra*_*ich 15
我们来看看前缀总和.一个[L, R]子阵列由3当且仅当divisble prefixSum[L - 1] mod 3 = prefixSum[R] mod 3.这个观察给出了一个非常简单的线性解(因为前缀sum mod 3只有3个可能的值,我们可以简单地找到第一个和最后一个).
例如,如果输入数组是{1,2,3,-4,-1},则前缀和为{0,1,0,0,2,1}.(由于前缀为空,因此有n + 1个前缀和).现在,您可以查看第一个和最后一个出现的0,1和2.