Привет 👋 ,
Предлагаю посмотреть решение задачи leetcode 1658. Minimum Operations to Reduce X to Zero
Дан целочисленный массив nums и число x. За одну операцию можно удалить крайний левый или крайний правый элемент из массива nums и вычесть его значение из x .
Внимание: Массив будет изменён для дальнейших операций.
Вернуть минимальное число операций, чтобы уменьшить x точно до 0, если это возможно, иначе вернуть -1
Пример 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: Оптимальное решение — удалить два последних элемента, чтобы уменьшить x до нуля.
Пример 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1
Пример 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: Оптимальное решение — удалить последние три элемента и первые два элемента (всего 5 операций), чтобы уменьшить x до нуля.
Ограничения
1 <= nums.length <= 10^5;
1 <= nums[i] <= 10^4;
1 <= x <= 10^9;
Решение
Рассмотрим, Пример 3
По условию задачи мы можем за одну операцию вычитать из заданного числа значение элемента из массива слева или справа.
Обозначим элементы слева как leftElements , элементы справа как rightElements. Подмассив, который остался обозначим как rest .
Таким образом, массив nums можно представить как:
[...leftElements, ...rest, ...rightElemets];
В примере,
leftElements = [3, 2] и их сумма 5,
rest = [20] и сумма элементов 20
rightElements = [1, 1, 3] и их сумма 5
x === 5 + 5 (сумма элементов leftElements и rightElemetns ). Если таких элементов нет, то возвращает -1 .
Сумму всех элементов обозначим как sum = 3 + 2 + 20 + 1 + 1 + 3 = 30 .
Таким образом, задача сводится к тому, чтобы найти подмассив rest максимальной длины, сумма элементов которого sumRest будет равна сумме всех элементов массива sum - x .
Будем проходить по массиву и использовать 2 индекса:
l ( left ) - индекс массива, который указывает на начало подмассива
r ( right ) - индекс массива, который указывает на окончания подмассива заданной суммы
currSum - текущая сумма элементов подмассив
maxLength - длина подмассива (r - l + 1)
При увеличении индекса r , currSum увеличивается на значение nums[r] . При увеличении индекса l , currSum уменьшается на значение nums[l-1] . currSum содержит актуальную сумму элментов подмассива.
Правая граница увеличивается на каждой итерации цикла, левая граница только тогда, когда выполняется условие currSum > sumRest .
Когда выполнено условие currSum === sumRest сохраняем значение длины подмассива. Если такое значение ранее уже было найдено (maxLength !== -1), то сравниваем длину и записываем наибольшую.
Когда значение правого индекса r равно длине массива nums.length - цикл закончен. Это условие выхода из цикла
Максимальная длина подмассива с заданной суммой элементов - сохранено в переменной maxLength . Чтобы найти число операций - нужно из длины исходного массива nums.length вычесть длину искомого подмассива maxLength .
Если подмассив не найден, то maxLength === -1 и метод вернёт -1
Решение целиком:
Ссылка на github
#leetcode #algorithms #javascript
