Минимум операций для уменьшения X до 0
Задача. Дан целочисленный массив nums и целое число x.
За одну операцию вы можете либо удалить крайний левый, либо крайний правый элемент из массива nums и вычесть его значение из x. Такая операция изменяет массив для будущих операций.
Верните минимальное количество операций, чтобы уменьшить x точно до 0, если это возможно, иначе верните -1.
- nums = [1, 1, 4, 2, 3], x = 5
Output: 2 (последовательно удаляем последние два элемента массива для уменьшения x до 0) - nums = [5, 6, 7, 8, 9], x = 4
Output: -1
Разбор
В этом разборе мы покажем способ, как одну задачу можно преобразовать в другую и решив ее, и получить нужный нам ответ.
Давайте найдем максимальный подмассив, сумма которого равна Sum, где Sum = TotalSum - X. Тогда длина этого максимального подмассива будет ответом на нашу исходную задачу, т.к. нам необходимо найти минимальное количество операций, чтобы уменьшить X до нуля.
Для того, чтобы найти максимальный подмассив, сумма которого равна Sum, воспользуемся методом двух указателей. Детали реализации смотрите в коде.