给定数组 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))

但是他要求优化it.I没通关

谁能给出提示？

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) 好。或许我们可以先对查询进行哈希处理或排序，因为彼此接近的查询在我们的搜索过程中表示范围很近，但我不确定如何做。

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) 的方向上扩展研究。如果你已经有太多的数字，继续求和是没有意义的...

所以你只用 j 和 i 在 A 上运行两次，每个 T 运行一次。这应该是 O(mn)。如果 diff = 0，您甚至可以中断循环。

给定数组 A 和 m 个查询

Given an array A and m queries

sorting

algorithm

query-optimization

minimum

binary-search