algorithm - 给定数组 A 和 m 个查询

Question

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

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

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

最小值

哪里|x|是 abs(x) 并且数组也可以有负数

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

所以会有 n*n 种可能的和。

这需要 O(n* n* log(n*n))

现在对于每个查询二分搜索 T 。那将是 O(m* log(n*n))

但是他要求优化，我没通关

谁能给出提示？

Answer 1

如果我们 sort the partial sums ，例如，

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 的绝对和差。我找不到引用来找到一对与常数最接近小于 O(n) time 的差值。 ，因此，这种方法似乎并不比 O(n * log n + n * m) 好。或许我们可以先对查询进行哈希处理或排序，因为在我们的搜索过程中，彼此接近的查询表示范围很近，但我不确定该怎么做。