Скользящее окно / Два указателя
При работе с массивами метод скользящего окна пользуется большой популярностью, поскольку позволяет эффективно решать задачи с использованием всего двух указателей. Основная идея этого подхода заключается в том, чтобы иметь левый и правый указатель и при необходимости сдвигать их в нужном направлении.
Представьте, что мы пытаемся найти подходящий подотрезок (subarray) в массиве: мы сдвигаем правый указатель как можно дальше, затем продвигаем левый поближе к правому. После этого снова двигаем правый указатель и снова корректируем левый. Повторяем этот процесс, пока не найдём лучший возможный подотрезок. Такой приём и называется «скользящее окно».
Задание – найти два числа, которые в сумме дают k
Дан отсортированный по возрастанию массив из
n чисел и целевое значение k. Нужно найти два числа из этого массива, которые в сумме дают k. При этом пользоваться словарями, map, hashmap и т. п. запрещается.Входные данные
Первая строка входных данных содержит два целых числа —
n (количество элементов в массиве, 1 ≤ n ≤ ) и число k . Следующая строка содержит n целых чисел, разделённых пробелом, которые представляют элементы массива в порядке возрастания.Выходные данные
Программа должна вывести два числа из массива, которые в сумме дают
k. Первым нужно напечатать наименьшее из этих двух. Если найти такие числа невозможно, следует вывести Impossible.Примеры
Входные данные | Выходные данные |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Учебный материал
Поскольку массив отсортирован по возрастанию, мы можем начать с двух указателей: один в начале массива, а другой — в самом конце, и регулировать их в зависимости от текущей суммы.
Если сумма этих двух элементов больше
k, то мы уменьшаем правый указатель, чтобы снизить сумму. Если сумма меньше k, то, наоборот, увеличиваем левый указатель, чтобы сумму повысить. И, наконец, если сумма ровно k, мы выводим эти элементы и завершаем программу.n, k = ... # Инициализируем n и k
a = ... # Инициализируем массив (упорядочен по возрастанию)
l, r = 0, len(a) - 1 # Инициализируем левый и правый указатели
while l < r: # Пока l и r не совпадают
if a[l] + a[r] > k: # Если сумма больше => уменьшаем её сдвигом r
r -= 1
elif a[l] + a[r] < k: # Если сумма меньше => увеличиваем её сдвигом l
l += 1
else: # a[l] + a[r] == k => выводим и завершаем
print(a[l], a[r])
break
else: # while...else означает, что не было break -> не нашли пару
print('Impossible')«Два указателя» — это общий метод, который можно адаптировать к самым разным задачам. Главная идея в том, чтобы правильно выбрать начальные позиции левого и правого указателей (они могут стоять совсем не там, где в данном примере) и логичное правило сдвига для каждого указателя (оно тоже может кардинально отличаться в зависимости от задачи).
В данном случае мы поставили левый указатель в начало массива, а правый — в самый конец. Но в другой задаче может понадобиться, чтобы оба указателя изначально стояли в начале массива, или чтобы левый был в самом конце, а правый начинал движение оттуда. Всё зависит от конкретной постановки задачи.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB