给定一个数组A和m个查询

Question

给定一个数组A和m个查询，每个查询是整数T

对于每个查询，请找到索引i和j，使得

| (|sum of elements from i to j| - T) |

最小值

其中|x|是绝对值符号，数组中可能包含负数。

我在面试中被问到了这个问题。我有一个解决方案，可以找到所有可能的和并存储它们的索引并排序。

所以可能有n*n个和。

这将需要O(n* n* log(n*n))的时间。

现在对于每个查询二分查找T。这将需要O(m* log(n*n))的时间。

但他要求进行优化。我没有通过面试。

有人能给出提示吗？

- Jitendra Kumhar

---

T可以是负数吗？ - Jim Mischel

数组的大小可以有多大？也许通过将总和存储在映射中以避免重复，可以提高平均情况性能。这会稍微减少总和的数量。将每个总和转换为正数，因为我们无论如何都要取绝对值。我考虑过线段树，但除非我们找到一种分解T的方法，否则这并没有帮助。 - nice_dev

我要求约束条件，但面试官要求先讲解方法。他说要将其减少到小于n*n。 - Jitendra Kumhar

由于我在我的方法中没有进一步考虑，所以我没有想到要问T的范围。你现在可以暂时将其视为正面的吗？对此我感到抱歉。 - Jitendra Kumhar

@JimMischel 对于负的T，我们的任务是最小化子数组和的绝对值，这有一个O(n log n)的解决方案。 - גלעד ברקן

请注意，O(log(n * n)) = O(log(n))，因此您可以简化一些表达式。 - ruakh

Answer 1

如果我们 对部分和进行排序，例如，

A  = [2, -4,  6, -3,  9]
ps = [2, -2,  4,  1, 10]

sorted = [-2, 1, 2, 4, 10]

最小绝对值和表示部分和之间的最小差异；在这种情况下，1和2表示总和：

-4 + 6 - 3 = -1

由于我们希望最小化另一个绝对值和，因此我们想要找到最接近 T 的绝对和差。我无法找到在 less than O(n) time 中找到与常数最接近的一对的参考资料，因此，目前而言，这种方法似乎并不比 O(n*log n+n*m) 更好。也许我们可以利用哈希或先对查询进行排序，因为彼此靠近的查询在搜索期间表示关闭范围，但我不确定如何做。

- גלעד ברקן

---

好的，谢谢。此外，复杂度将是O(n * log n + m * log n)，其中m是查询数量。 - Jitendra Kumhar

如果T=9或大于9的情况下会怎样？ - Jitendra Kumhar

@JitendraKumhar 你说得对。对部分和的差进行排序并不是正确的方法，因为它们有O(n^2)个。相反，我们需要在这些差值中进行搜索。我会进行编辑。 - גלעד ברקן

我接受这个答案，因为我认为这是可以达到的最好结果。同时，我认为面试官也期望得到这个答案。 - Jitendra Kumhar

@JitendraKumhar 听起来不错。谢谢你让我知道。另外，我在考虑提到，虽然我通常不喜欢这种解决方案，但是如果范围足够有限，我认为我们也可以用FFT更有效地记录所有前缀和可能性，并以此方式进行排序和搜索。 - גלעד ברקן

Answer 2

编辑：我想解决所有的问题实际上是巨大的浪费。只有当m >> n时才有趣。否则，这是我的解决方案。

想象一场乌龟和兔子之间的比赛。我希望你知道这个故事......所以兔子“i”让乌龟“j”先走。他知道自己跑得更快，可以小睡一会儿。他只担心乌龟是否已经看不见了，“T”米远，然后他会很快地跑，直到他看到乌龟再次睡觉......如此往复。

因此初始化

i = 0
j = 0
bestval = inf
index = none
diff = T

主循环

while(true):
    if diff < 0:
        i++
        diff += A[i] 
    elif j==n:
        break
    else: 
        j++
        diff += A[j]

    # record best distance
    if abs(diff) < bestval:
       bestval = diff
       index = (i, j)

你不能因为没有在增加abs(diff)的方向上进行研究而错过最佳选择。如果你已经有了太多的数字，那么继续求和是毫无意义的...

所以你只需要对A进行两次运行，分别针对j和i，每个T运行一次。这应该是O(mn)的。如果diff = 0，你甚至可以中断循环。

- Vince

---

我不明白我们如何能够保证在不回溯i的情况下找到最佳差异（使您的想法每次查询的复杂度为O(n^2)）。请问您能解释一下，为什么在迭代j时只需要增加而不需要减少i呢？ - גלעד ברקן

如果数组中有负数，这段代码就无法正常工作。 - Matt Timmermans

哦，你说得对，我忽略了A可能是负数。这个解决方案无法检测到一个远为负的数字，它可以最优地平衡总和。 - Vince