Java-решение LeetCode   —  209. Сумма подмассива минимального размера

Нам дан массив положительных целых чисел, называемый nums, и положительное целое число, называемое target. Нам нужно найти наименьшую длину подмассива в пределах «nums», сумма которого больше чем или равно «target». Если нет подмассива, соответствующего требованиям, мы возвращаем 0.

Что такое подмассив?

Массив, являющийся частью другого массива, элементы которого соседствуют друг с другом.

Пример:

мойМассив: [1, 3, 5, 8, 2, 4]

мойПодмассив: [3, 5, 8]

Итак, для этой задачи давайте сформируем входной массив с именем «nums» и целевое число с именем «target». Затем мы решаем выходные данные, находя наименьшую длину подмассива из массива «nums», сумма которого больше или равна «цели».

Пример:

цель: 4

числа: [2, 4, 4]

Вывод: наименьшая длина будет равна 1.

Обратите внимание, что выходным значением является 1, поскольку после просеивания элементов мы видим, что подмассив [4] длиной 1 представляет собой наименьшую длину, сумма которой больше или равна целевому числу 4. Следовательно, 1 будет наименьшая длина подмассива.

Описание проблемы

Далее давайте перечислим несколько шагов, которые нам понадобятся для решения этой проблемы:

Шаг 1) определение размера массива

Шаг 2) выяснить, как перемещаться по массиву, метод двух указателей с циклами

Шаг 3) выясните, как отслеживать сумму чисел, чтобы найти минимальную длину подмассива и минимальную длину каждого подмассива.

Шаг 4) обратите внимание на все ограничения.

Шаг 5) нарисуйте концепцию

Затем , соберите все это вместе на языке программирования!

Описание проблемы

Шаг 1)Чтобы найти размер массива, мы можем использовать атрибут длины класса Array:

nums.length

Шаг 2)Чтобы выяснить, как пройти по каждому числу в массиве, мы можем использовать различные методы. Для решения этой задачи мы воспользуемся методом двух указателей.

Шаг 3)Поскольку мы используем метод двух указателей, мы можем отслеживать сумму чисел и минимальную длину подмассива в циклах while, обновляя переменные во время итерации по массиву.

Шаг 4)Некоторыми ограничениями, которые следует учитывать, являются подмассивы, которые не найдены с целевым числом, поэтому мы можем установить переменную и сказать:

if (min_length == Integer.MAXVALUE)

  return 0;

Шаг 5)Что касается кодирования, мы хотим устранить ограничение пустого массива и любых переменных и циклов, которые нам понадобятся. Кроме того, в цикле нам нужно переместить указатель и обновить переменные, чтобы найти целевую сумму и минимальную длину подмассива в соответствии с этой суммой. Наконец, мы возвращаем минимальную длину подмассива.

Объяснение кода

Заголовок метода:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

Ограничение пустого массива:

        if (nums.length == 0)
            return 0;

Объявите два указателя, переменную суммы и переменную минимальной длины.

        int i = 0;
        int j = 0;
        int sum = 0;
        int min_length = Integer.MAX_VALUE;

Сначала заголовок цикла while с указателем j:

        while (j < nums.length){

Обновить переменную суммы для элемента с индексом j, указатель j перемещается на один индекс вверх:

            sum = sum + nums[j++];

Если обнаружено, что сумма больше или равна целевой, введите еще один цикл while и найдите минимальное значение между min_length и двумя указателями. Затем снова обновите сумму и переместите указатель i на один индекс вверх в массиве:

            while (sum >= target){
                min_length = Math.min(min_length, j - i);
                sum = sum - nums[i++];
            }
        }

Проверьте, изменилась ли переменная min_length, верните 0, если изменений нет, верните переменную минимальной длины, если она изменилась:

        if (min_length == Integer.MAX_VALUE)
          return 0;
        else
          return min_length;
    }
}

Полный код:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0)
            return 0;

        int i = 0;
        int j = 0;
        int sum = 0;
        int min_length = Integer.MAX_VALUE;
        while (j < nums.length){
            sum = sum + nums[j++];

            while (sum >= target){
                min_length = Math.min(min_length, j - i);
                sum = sum - nums[i++];
            }
        }

        if (min_length == Integer.MAX_VALUE)
          return 0;
        else
          return min_length;
    }
}

Благодарность принадлежит специалисту по решению проблем jeantimex на LeetCode и их решению. В этой ветке обсуждения есть больше ответов с хорошими объяснениями этой проблемы.

Спасибо за прочтение!