Найти первое минимальное окно массива

Question

Для целочисленного массива окно [a, b] состоит из элементов массива между a и b, а размер окна b - a.Теперь вы должны найти первое минимальное окно, между которым есть N / 2 элементов (N - размер массива, b - больше, чем a).
Например, {5, -3,10, 12, -2, -5}, мы получаем ответ [-5, -2].

Answer 1

Если я хорошо понимаю, вы должны найти первое окно длины N / 2, которое имеет наименьшую сумму.

Вы можете достичь этого, испробовав все возможные окна такой длины и сохранив самые маленькие из найденных к настоящему времени. Если вы делаете это умным способом, у вас может быть алгоритм сложности O (N). Поскольку это, кажется, домашнее задание, я позволю тебе разобраться сам;)

Answer 2

Одно решение:
a.Узнайте N (в O (N) время)
б.Пройдите по массиву и для каждого элемента x _i найдите N / 2 - x _i в хэше / карте.Если найдено, у вас есть решение, иначе вставьте N / 2 - x _i во время хэша / карты (O (n) при использовании хеша или O (nlogn) при использовании карты и пространства O (n).).