假设有两个长度相同的数组[an]和[bn]，求是否有[an]和[bn]两个子数组，使得子数组的和相同且长度相同。例如:[an] = [5,4,17,10,29], [bn]=[1,22,23,4,15]，程序会返回“yes”，因为[17,10]在[ [bn] 中的 an] 和 [23,4] 具有相同的总和和相同的长度。有没有比 O(n^3) 更好的算法？
最佳答案
(好吧，如果我指出一个 O(n^2) 版本，也许我会向做得更好的人学习)。假设对于每个数组，您计算前 k 个元素的总和，对于所有 k = 1 到数组长度，以便 [5,4,17,10,29] 变成 [5,9,26,36,65 ].显然，只需保持总计，您就可以在 O(n) 中做到这一点。
现在您可以通过从另一个中减去一个运行总和来计算该数组的任何部分的总和，例如17 + 10 = 36 - 9。因此您可以在时间 O(n^2) 内计算出所有连续子数组的 O(n^2) 和。将一个子数组的结果输入哈希表，然后计算另一个子数组的所有结果，并检查它们是否在哈希表中。哈希表操作(概率)为 O(1)，因此总成本为 O(n^2)
关于algorithm - 找到总和相同且长度相同的子数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28059216/