Leetcode 2348: количество заполненных нулями подмассивов

Как подсчитать количество заполненных нулями подмассивов в TypeScript

При работе с массивами часто возникают проблемы, требующие подсчета количества подмассивов, соответствующих определенным критериям. В этой статье мы обсудим решение TypeScript для подсчета количества подмассивов, заполненных 0 в целочисленном массиве. Мы предоставим пошаговое объяснение кода, а также его временные и пространственные сложности.

Постановка задачи

Учитывая целочисленный массив nums, нам нужно подсчитать количество подмассивов, заполненных 0. Подмассив — это непрерывная непустая последовательность элементов в массиве.

Пример

Предположим, nums = [1,3,0,0,2,0,0,4]. Тогда вывод должен быть 6. Существует 4 вхождения [0] в качестве подмассива. Есть 2 вхождения [0,0] в качестве подмассива. Подмассив размером более 2, заполненный 0, не встречается. Поэтому мы возвращаем 6.

Решение

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

Вот код TypeScript для того же самого:

function zeroFilledSubarray(nums: number[]): number {
  // Initialize the count for the number of subarrays that have a sum of zero
  let count = 0;
  // Initialize the count for the number of consecutive zeros in a subarray
  let currentCount = 0;
  // Iterate through the array
  for (let i = 0; i < nums.length; i++) {
    // If the current element is zero
    if (nums[i] === 0) {
      // Increment the current count
      currentCount++;
      // Add the current count to the total count
      count += currentCount;
      // If the current element is not zero
    } else {
      // Reset the current count to zero
      currentCount = 0;
    }
  }
  // Return the total count
  return count;
}

Разберем код построчно:

Мы определяем функцию zeroFilledSubarray, которая принимает массив целых чисел nums и возвращает число.
Мы инициализируем две переменные count и currentCount равными 0.
Мы перебираем массив nums, используя цикл for.
Если текущий элемент nums равен 0, мы увеличиваем currentCount на 1 и добавляем его к count. Это потому, что мы нашли подмассив последовательных нулей, и нам нужно добавить количество этого подмассива к общему количеству.
Если текущий элемент nums не равен 0, мы сбрасываем currentCount в 0. Это потому, что если мы встретим ненулевой элемент, текущий подмассив последовательных нулей будет нарушен.
Наконец, мы возвращаем количество всех подмассивов, заполненных 0.

Сложность времени

Временная сложность приведенной выше функции равна O(n), где n — длина заданного массива nums. Это потому, что мы проходим весь массив только один раз.

Космическая сложность

Объемная сложность приведенной выше функции составляет O(1), поскольку мы не используем никаких дополнительных структур данных для вычислений.

Выполнение

Давайте посмотрим на некоторые детали реализации приведенного выше кода:

Машинопись

TypeScript — это надмножество JavaScript, которое добавляет в язык необязательную статическую типизацию и другие функции. Он набирает популярность среди разработчиков из-за безопасности типов, улучшенного инструментария и лучшей организации кода.

В приведенном выше коде мы определяем функцию zeroFilledSubarray с помощью TypeScript. Мы указываем тип входного параметра nums как массив целых чисел, а возвращаемый тип функции как число.

Перебор массива

В приведенном выше коде мы используем цикл for для перебора заданного массива nums. Мы начинаем цикл с индекса 0 и продолжаем до конца массива nums, используя свойство длины массива.

Подсчет подмассивов

Чтобы подсчитать количество подмассивов, заполненных 0, мы используем две переменные count и currentCount. Мы инициализируем обе эти переменные равными 0. Мы используем currentCount для отслеживания количества последовательных нулей, с которыми мы столкнулись до сих пор.

Если текущий элемент nums равен 0, мы увеличиваем currentCount на 1 и добавляем его к count. Это потому, что мы нашли подмассив последовательных нулей, и нам нужно добавить количество этого подмассива к общему количеству.

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

Возврат счета

Наконец, мы возвращаем значение count. Это общее количество всех подмассивов, заполненных 0 в данном массиве nums.

Заключение

В этой статье мы обсудили решение TypeScript для подсчета количества подмассивов, заполненных 0 в целочисленном массиве. Мы объяснили код построчно и указали его временные и пространственные сложности. Мы также рассмотрели некоторые детали реализации кода, включая TypeScript, перебор массива и подсчет подмассивов. Мы надеемся, что вы нашли эту статью познавательной и полезной.