Мінімальний розмір підмасиву з сумою — leetcode #209: Покроковий посібник

Задача «Мінімальний розмір підмасиву з сумою» є класичним завданням для використання техніки «ковзаючого вікна» (sliding window), яке перевіряє вашу здатність ефективно працювати з підмасивами. Розглянемо її детальніше і реалізуємо на Java.

Умови задачі

Дано масив додатних цілих чисел nums та додатне ціле число target. Потрібно повернути мінімальну довжину підмасиву [nums[l], nums[l+1], ..., nums[r-1], nums[r]], сума елементів якого більша або дорівнює target. Якщо такого підмасиву немає, поверніть 0.

Приклад 1:

Вхід:
target = 7; nums = {2, 3, 1, 2, 4, 3};

Вихід: 2

Пояснення:
Підмасив [4, 3] має мінімальну довжину 2 і суму 7.

Приклад 2:

Вхід:
target = 4; nums = {1, 4, 4};

Вихід: 1

Пояснення:
Підмасив [4] відповідає вимогам з довжиною 1.

Приклад 3:

Вхід:
target = 11; nums = {1, 1, 1, 1, 1, 1, 1, 1};

Вихід: 0

Пояснення:
Жоден підмасив не має суми, яка дорівнює або перевищує 11.

Підхід до розв'язку задачі

Спостереження:

1. Техніка ковзаючого вікна (sliding window) добре підходить для цього завдання:

• Вікно розширюється, поки сума елементів не досягне або не перевищить цільове значення.
• Як тільки сума достатня, зменшуємо розмір вікна зліва, щоб мінімізувати його розмір.

1. Мінімальна довжина підмасиву оновлюється, коли сума вікна задовольняє умови.

Алгоритм:

1. Ініціалізуємо:

• Два вказівники start та end для ковзаючого вікна.
• Змінну sum для зберігання суми поточного вікна.
• Змінну minLength, ініціалізовану дуже великим значенням.

1. Проходимо масив за допомогою вказівника end:

• Додаємо nums[end] до sum.
• Поки sum >= target:

Оновлюємо minLength на менше з його поточного значення або розміру вікна (end - start + 1).

• Віднімаємо nums[start] від sum і збільшуємо start, щоб зменшити вікно.

1. Повертаємо minLength, якщо воно було оновлено; в іншому випадку — повертаємо 0.

Реалізація на Java

Ось рішення на Java:

public class MinimumSizeSubarraySum {  
 public static int minSubArrayLen(int target, int[] nums) {  
 int minLength = Integer.MAX_VALUE;  
 int sum = 0;  
 int start = 0;  

 for (int end = 0; end < nums.length; end++) {  
 sum += nums[end]; // Розширюємо вікно, додаючи поточний елемент  

 while (sum >= target) { // Зменшуємо вікно, поки сума не стане меншою за target  
 minLength = Math.min(minLength, end - start + 1);  
 sum -= nums[start];  
 start++;  
 }  
 }  

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

 public static void main(String[] args) {  
 int[] nums1 = {2, 3, 1, 2, 4, 3};  
 int target1 = 7;  
 System.out.println(minSubArrayLen(target1, nums1)); // Вихід: 2  

 int[] nums2 = {1, 4, 4};  
 int target2 = 4;  
 System.out.println(minSubArrayLen(target2, nums2)); // Вихід: 1  

 int[] nums3 = {1, 1, 1, 1, 1, 1, 1, 1};  
 int target3 = 11;  
 System.out.println(minSubArrayLen(target3, nums3)); // Вихід: 0  
 }  
}

Аналіз складності

Часова складність:

• Вказівник end проходить масив лише один раз.
• Вказівник start також рухається вперед не більше ніж n разів.
• Загальна часова складність: O(n).

Просторова складність:

• Рішення використовує постійну кількість додаткової пам'яті.
• Просторова складність: O(1).

Ключові висновки для Java-розробників

1. Техніка ковзаючого вікна (sliding window) є потужною для задач, що включають обробку підмасивів.
2. Ефективне управління розміром вікна дозволяє мінімізувати зайві обчислення.
3. Враховуйте крайні випадки:

• Масиви, всі елементи яких менші за target.
• Масиви, що містять лише один елемент, рівний або більший за target.

Приклад поетапного розв'язку:

Вхід:

target = 7;  
nums = {2, 3, 1, 2, 4, 3};

1. Початкові налаштування:

• start = 0, end = 0, sum = 0, minLength = Integer.MAX_VALUE.

1. Розширюємо вікно:

• Додаємо 2: sum = 2.
• Додаємо 3: sum = 5.
• Додаємо 1: sum = 6.
• Додаємо 2: sum = 8.

Зменшуємо вікно:

• Віднімаємо 2: sum = 6, start = 1.
• Віднімаємо 3: sum = 3, start = 2.

1. Додаємо 4: sum = 7. Зменшуємо вікно:

• Віднімаємо 1: sum = 6, start = 3.

1. Додаємо 3: sum = 9. Зменшуємо вікно:

• Віднімаємо 2: sum = 7, start = 4.

Результат: Мінімальний підмасив — [4, 3] з довжиною 2.

Завдання для практики, щоб закріпити концепцію

1. Максимальна сума підмасиву розміру K (ковзаюче вікно)
2. Добуток елементів підмасиву менший за K
3. Найдовший підрядок без повторюваних символів

Такий структурований підхід та ефективна реалізація на Java допоможуть вам оволодіти проблемою «Мінімальний розмір підмасиву з сумою». Успіхів у програмуванні!

Перекладено з: Minimum Size Subarray Sum — leetcode #209 : A Step-by-Step Guide