Задачи
October 3

Минимум операций для уменьшения X до 0

Задача. Дан целочисленный массив nums и целое число x.
За одну операцию вы можете либо удалить крайний левый, либо крайний правый элемент из массива nums и вычесть его значение из x. Такая операция изменяет массив для будущих операций.

Верните минимальное количество операций, чтобы уменьшить x точно до 0, если это возможно, иначе верните -1.

Примеры:

  1. nums = [1, 1, 4, 2, 3], x = 5
    Output: 2 (последовательно удаляем последние два элемента массива для уменьшения x до 0)
  2. nums = [5, 6, 7, 8, 9], x = 4
    Output: -1

Разбор

В этом разборе мы покажем способ, как одну задачу можно преобразовать в другую и решив ее, и получить нужный нам ответ.

Давайте найдем максимальный подмассив, сумма которого равна Sum, где Sum = TotalSum - X. Тогда длина этого максимального подмассива будет ответом на нашу исходную задачу, т.к. нам необходимо найти минимальное количество операций, чтобы уменьшить X до нуля.

Для того, чтобы найти максимальный подмассив, сумма которого равна Sum, воспользуемся методом двух указателей. Детали реализации смотрите в коде.

Реализация

Play-test

https://dotnetfiddle.net/156BGR