Наименьший подмассив с заданной суммой

Наименьший подмассив с заданной суммой

Условие задачи

Дан массив положительных чисел и положительное число s. Найдите длину наименьшего непрерывного подмассива, сумма которого больше либо равна s. Если такого подмассива нет, верните 0.

Пример 1:

1
2
3

Вход: [2, 1, 5, 2, 3, 2], s=7
Выход: 2
Пояснение: наименьший подходящий подмассив — [5, 2].

Пример 2:

1
2
3

Вход: [2, 1, 5, 2, 8], s=7
Выход: 1
Пояснение: наименьший подходящий подмассив — [8].

Пример 3:

1
2
3

Вход: [3, 4, 1, 1, 6], s=8
Выход: 3
Пояснение: подходят подмассивы [3, 4, 1] и [1, 1, 6].

Решение

Размер окна в этой задаче не фиксирован:

  1. Расширяем окно вправо и прибавляем очередной элемент к его сумме.
  2. Как только сумма становится не меньше s, запоминаем длину окна, если она меньше найденной ранее.
  3. Затем вычитаем левый элемент и сдвигаем левую границу вправо. Продолжаем сжимать окно, пока его сумма не станет меньше s.

Каждый элемент входит в окно и выходит из него не более одного раза.

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package main

import "fmt"

func smallestSubarrayWithGivenSum(s int, arr []int) int {
	minLength := len(arr) + 1
	windowSum := 0
	windowStart := 0

	for windowEnd, value := range arr {
		windowSum += value

		for windowSum >= s {
			windowLength := windowEnd - windowStart + 1
			if windowLength < minLength {
				minLength = windowLength
			}
			windowSum -= arr[windowStart]
			windowStart++
		}
	}

	if minLength == len(arr)+1 {
		return 0
	}
	return minLength
}

func main() {
	fmt.Println("Длина наименьшего подмассива:", smallestSubarrayWithGivenSum(7, []int{2, 1, 5, 2, 3, 2}))
	fmt.Println("Длина наименьшего подмассива:", smallestSubarrayWithGivenSum(7, []int{2, 1, 5, 2, 8}))
	fmt.Println("Длина наименьшего подмассива:", smallestSubarrayWithGivenSum(8, []int{3, 4, 1, 1, 6}))
}

Вывод:

1
2
3

Длина наименьшего подмассива: 2
Длина наименьшего подмассива: 1
Длина наименьшего подмассива: 3

Временная сложность

Внешний цикл проходит по всем элементам, а внутренний цикл обрабатывает каждый элемент не более одного раза. Поэтому временная сложность равна \(O(N+N)\), то есть \(O(N)\).

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).