Дан массив A и m запросов

Question

Учитывая массив A и m запросов каждый запрос является целым числом T

Для каждого запроса найдите индекс i и j такой, что

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

это минимум

где | х | является abs (x), и массив также может иметь отрицательные числа

Мне задали этот вопрос в интервью Directi. У меня было решение найти все возможные суммы и сохранить их индексы и отсортировать.

поэтому возможно n * n сумм.

Это заняло бы O (n * n * log (n * n))

теперь для каждого запроса бинарный поиск T. Это будет O (m * log (n * n))

Но он попросил оптимизировать его. Я не очистил раунд.

Кто-нибудь может дать подсказку по этому поводу?

Answer 1

РЕДАКТИРОВАТЬ: Я полагаю, что решение всех сумм на самом деле огромная работа впустую. Это интересно только если m >> n. Еще вот мое решение.

Представьте себе гонку между зайцем и черепахой. Я надеюсь, что вы знаете эту историю ... Таким образом, Заяц "я" позволяет черепахе "J" идти первым. Он знает, что он быстрее и что он может вздремнуть. Он беспокоится, только если Черепаха скрыта из виду, «Т» метров дальше, затем он очень быстро бежит, пока не увидит Черепаху и снова не заснет ... И так далее.

Итак, инициализация

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.

Answer 2

Если мы отсортируем частичные суммы , например,

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) время , так что, как представляется, этот подход не выглядит лучше, чем O (n * log n + n) * м). Возможно, мы можем сначала воспользоваться хэшированием или сортировкой запросов, так как запросы, близкие друг к другу, представляют близкие диапазоны во время нашего поиска, но я не уверен, как это сделать.