Модуль: Два указателя


Задача

1 /11


Метод двух указателей

Теория Нажмите, чтобы прочитать/скрыть


Два указателя

Метод двух указателей широко используется при решении различных задач, в которых асимптотика не должна превышать O(n).
Рассмотрим идею метода двух указателей на примере следующей задачи.
 
Задача
В массиве неотрицательных чисел необходимо найти любой непрерывный отрезок с суммой элементов, равной k.

В методе двух указателей, указателями называются индексы начала и конца рассматриваемого отрезка (а не в смысле того, что они имеют тип pointer).

Решить задачу методом двух указателей можно, если на каждом шаге алгоритма мы можем перемещать один из указателей вправо. Другими словами, при увеличении значения одного указателя значение другого указателя может только увеличиваться. Таким образом, мы не перебираем все значения отрезка заново, а может просто продолжать вычисления с предыдущего значения.
Так как мы двигаем два указателя от начала массива к концу, то каждый из них будет принимать не более n значений. Следовательно, количество действий алгоритмы не превысит 2n и ассимптотика алгоритма останется O(n).

Идея решения данной задачи будет заключаться в следующем.
1) Зафиксируем первый (i) и второй (j) указатель на первом элементе массива.
2) Начальное значение суммы положим равным первому элементу массива (на который указывают оба указателя).
3) Далее, будем двигать правый указатель (j) и добавлять к сумме значения элементов a[j]. После добавления очередного элемента у нас сумма может стать либо больше, либо равной искомой (если она меньше искомой, то мы будем дальше добавлять значения элементов к сумме).
- Если на текущем шаге сумма элементов станет равной искомому значению, значит мы получили наш ответ (нужные значения i и j.
- Если сумма элементов на текущем шаге стала больше искомого значения, значит необходимо из суммы убрать один элемент. Какой? Очевидно, что тот, на который указывает левый указатель i. Тогда уберем из суммы данный элемент a[i] и увеличим значение i. 4) Так будем действовать до тех пор, пока либо не найдем искомую сумму, либо правый указатель не дойдет до конца массива. Один из вариантов реализации данной идеи представлен в программе ниже (язык Python).
n = 5
target = 7
nums = [1, 2, 3, 4, 5]

i = 0
j = 0
s = nums[j]
while j < n:
    if s == target:
        break
    if s < target:
        j += 1
        if j < n:
            s += nums[j]
    else:
        s -= nums[i]
        i += 1

if s == target:
    print(i, j)
else:
    print(-1, -1)

Задача

Дан массив из N положительных чисел. Найти в нем минимальное количество подряд идущих чисел, таких что их сумма больше K.

Входные данные
В первой строке записано число N, во второй - K (0<N<= 106, 0<=K<= 109). В третьей строке записаны натуральные числа последовательности.

Выходные данные
Выведите длину наименьшей последовательности чисел, сумма которых больше K. Если такой последовательности найдено не будет, то выведите -1.
 
Примеры
Входные данные Выходные данные
1 6
7
3 1 3 2 4 3
3

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64208
C#1
Java2
Python369
Комментарий учителя