Если вы планируете совершенствовать свои навыки решения задач на основе шаблона скользящего окна, на мой взгляд, это лучшая отправная точка. Это также важно, поскольку эти технологические компании (Goldman Sachs, Meta, Amazon и Google) задавали этот вопрос.
Важная вещь, которую следует вынести из этой статьи, — когда мы должны использовать шаблон скользящего окна. Мы уже обсуждали похожую проблему Самая длинная повторяющаяся строка после K замен.
Эта статья относится к плану подготовки к собеседованию, который вы можете найти здесь.
Итак, Лос-Гехт.
Содержание
Описание
Вам дан массив целых чисел 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 — это размер массива, у нас будет 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; | |
| } |
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 долларов США в месяц и поддерживает всех авторов.
Вы также можете подписаться на меня ЗДЕСЬ, чтобы получать новости о моих историях.
