Сложность: medium
Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.
Пример:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
👨💻 Алгоритм:
1️⃣Инициализация переменных: Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0. Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.
2️⃣Итерация по массиву: Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации: Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right]. Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.
3️⃣Возврат результата: Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1. Верните res.
😎 Решение:
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
right = 0
sumOfCurrentWindow = 0
res = float('inf')
for right in range(0, len(nums)):
sumOfCurrentWindow += nums[right]
while sumOfCurrentWindow >= target:
res = min(res, right - left + 1)
sumOfCurrentWindow -= nums[left]
left += 1
return res if res != float('inf') else 0
Ставь 👍 и забирай 📚 Базу знаний