209. Minimum Size Subarray Sum

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int left = 0, sumOfCurrentWindow = 0;
        int res = int.MaxValue;
        for (int right = 0; right < nums.Length; right++) {
            sumOfCurrentWindow += nums[right];
            while (sumOfCurrentWindow >= target) {
                res = Math.Min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }
        return res == int.MaxValue ? 0 : res;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sumOfCurrentWindow = 0;
        int res = int.MaxValue;
        for (int right = 0; right < nums.size(); right++) {
            sumOfCurrentWindow += nums[right];
            while (sumOfCurrentWindow >= target) {
                res = min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }
        return res == int.MaxValue ? 0 : res;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sumOfCurrentWindow = 0;
        int res = Integer.MAX_VALUE;

        for(right = 0; right < nums.length; right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = Math.min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left++];
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

class Solution {
    minSubArrayLen(target, nums) {
        let left = 0, sumOfCurrentWindow = 0;
        let res = Number.MAX_VALUE;

        for (let right = 0; right < nums.length; right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = Math.min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }

        return res === Number.MAX_VALUE ? 0 : 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

func minSubArrayLen(target int, nums []int) int {
    left, sumOfCurrentWindow, res := 0, 0, int(^uint(0) >> 1)

    for right := 0; right < len(nums); right++ {
        sumOfCurrentWindow += nums[right]

        for sumOfCurrentWindow >= target {
            if res > right - left + 1 {
                res = right - left + 1
            }
            sumOfCurrentWindow -= nums[left]
            left++
        }
    }

    if res == int(^uint(0) >> 1) {
        return 0
    }
    return res
}

Algorithm

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.

😎