Если вы планируете совершенствовать свои навыки решения задач на основе шаблона скользящего окна, на мой взгляд, это лучшая отправная точка. Это также важно, поскольку эти технологические компании (Goldman Sachs, Meta, Amazon и Google) задавали этот вопрос.

Важная вещь, которую следует вынести из этой статьи, — когда мы должны использовать шаблон скользящего окна. Мы уже обсуждали похожую проблему Самая длинная повторяющаяся строка после K замен.

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

Итак, Лос-Гехт.

Содержание

  1. Описание
  2. Подход грубой силы
  3. Подход скользящего окна
  4. Код
  5. Сложность времени и пространства

Описание

Вам дан массив целых чисел A и целое число target, и вы должны найти наименьший подмассив A, такой, что сумма его элементы больше или равны целевому.

Если такого подмассива не существует, выведите 0.



Пример 1:

Input: [4, 1, 6, 2, 3] and target = 8
Output: 2
Explanation: The smallest subarray with sum greater or equal to 8 is [2, 6].

Пример 2:

Input: [2, 2, 2, 2] and target = 10
Output: 0
Explanation: No subarray exists whose sum is greater or equal to 10.

Подход грубой силы

Мы можем наивно пройтись по каждому подмассиву, n — это размер массива, у нас будет подмассивов. Для каждого подмассива мы найдем сумму его элементов и запомним размер наименьшего подмассива с общей суммой, превышающей или равной нашей целевой.

Наивный алгоритм

  • Используйте два цикла for для обхода каждого подмассива, где внешний цикл будет указывать на начало, а внутренний цикл — на конец подмассива.
  • Используйте другой цикл, чтобы суммировать элементы текущего подмассива.
  • Если сумма больше или равна целевому, а размер текущего подмассива меньше нашего минимального размера на данный момент, то обновите минимальный размер до текущего размера подмассива.

Здесь временная сложность будет кубической, O(n³) по своей природе, потому что мы используем три вложенных цикла, два внешних цикла for предназначены для обхода подмассивов, а самый внутренний цикл используется для получения суммы текущего подмассива.

Пока мы этим занимаемся, давайте посмотрим на его код. Я хорошо прокомментировал код, поэтому, если C++ не является вашим основным языком, вы все равно можете понять, что происходит.

Код

#include <bits/stdc++.h> // header files
using namespace std;
// coded by ganesh prasad
// read - ganeshpr227.medium.com
int minSub(int target, vector<int> input)
{
// define a variable to hold the minimum size
// and initialize it with a mzimum value possible
int minimum = std::numeric_limits<int>::max();
// declare two variables to point the start and end
// of a subarray
int start = 0, end = 0;
// the outer loop points to the start of every subarray
for (start = 0; start < input.size(); start++)
{
// the inner loop points the end of every subarray
for (end = start; end < input.size(); end++)
{
// use this for loop to sum the elements of current
// subarray
int total = 0;
for (int i = start; i <= end; i++)
{
total += input[i];
}
// check if the total is greater or equal to target
if (total >= target)
{
// then update the minimum answer
minimum = min(minimum, end - start + 1);
}
}
}
// if there is no such subarray then return 0
// in other words if our minimum is unchanged
if (minimum == std::numeric_limits<int>::max())
return 0;
return minimum;
}
// driver program
int main()
{
int target = 8;
vector<int> input{4, 3, 1, 2, 6};
cout << "The length of the smallest subarray with target " << target << " is ";
cout << minSub(8, input) << endl;
return 0;
}
view raw minSubarray.cpp hosted with ❤ by GitHub
Output:
The length of the smallest subarray with target 8 is 2

Конечно, мы можем улучшить его с O(n³) до O(n²); если мы предварительно обработаем список и получим массив сумм префиксов (O(n)), то получение суммы любого подмассива будет постоянной операцией (следующий рисунок).

Теперь давайте посмотрим на магию и поймем простое решение с линейной сложностью.



Раздвижное окно

Стратегия решения этой задачи аналогична Подмассив максимальной суммы размера K, и в этом подходе, как следует из названия, мы перемещаем окно слева направо и меняем размер окна в соответствии с нашими потребностями. потребности. Окном в массиве можно управлять с помощью двух переменных, одна из которых указывает на начало, а другая — на конец.

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

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

Этот процесс завершится, как только последний элемент массива будет добавлен в скользящее окно.

Давайте посмотрим на это на примере.

Его код так же прост, как и само решение. Он хорошо прокомментирован (чтобы сделать его независимым от языка) и написан на С++.

Код

#include <bits/stdc++.h> // header files
using namespace std;
int minSubSliding(int target, vector<int> &nums)
{
// define a variable for minimum size
// and set it to maximum integer possible
int min = std::numeric_limits<int>::max();
// a variable to hold running sum
int total = 0;
// variable to hold start and end index of our subarray / window
int start = 0, end = 0;
// use a for loop to add new elements into the window
for (end = 0; end < nums.size(); end++)
{
// add the current element into the total sum of the subarray
total += nums[end];
// if the total of the subarray is greater or equal to target
// and since we need the minimum subarray start decreasing the
// size from left
while (total >= target)
{
// update the minimum length of our window if length of our current
// window is smaller
if (end - start + 1 < min)
{
min = end - start + 1;
}
// decrease the size from left or shrink the window
total -= nums[start];
start++;
}
}
// when there is no such window with sum greater or equal to target
// then our min will remain unchange, if it is unchanged then return 0
if (min == std::numeric_limits<int>::max())
return 0;
return min;
}
// driver program
int main()
{
int target = 8;
vector<int> input{4, 3, 1, 2, 6};
cout << "The length of the smallest subarray with target " << target << " is ";
cout << minSubSliding(8, input) << endl;
return 0;
}
Output:
The length of the smallest subarray with target 8 is 2

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

Время: мы видим, что внешний цикл for добавляет каждый элемент только один раз, а внутренний цикл while удаляет (если он это делает) только один раз, поэтому данный подход является линейным, O (n) по своей природе.

Пространство: мы не используем пространство для этого алгоритма, поэтому его пространственная сложность постоянна, O(1).

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

Я надеюсь, что эта статья была вам полезна.

Если вам понравилось то, что вы только что прочитали, мы будем очень признательны за хлопки🤗🤗🤗. Вы можете щедро хлопать в ладоши; это показывает мне, насколько вам понравилась эта история. А если не понравилось? Пожалуйста, оставьте комментарий😋!

P.S.: Если вам нравится этот непрерывный опыт чтения на этой прекрасной платформе Medium.com, подумайте о том, чтобы поддержать авторов этого сообщества, подписавшись на членство ЗДЕСЬ. Он стоит всего 5 долларов США в месяц и поддерживает всех авторов.

Вы также можете подписаться на меня ЗДЕСЬ, чтобы получать новости о моих историях.