---

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

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

Пример 1:

Вход: [2, 5, 3, 10], target=30
Выход: [2], [5], [2, 5], [3], [5, 3], [10]
Пояснение: существует шесть подходящих непрерывных подмассивов.

Пример 2:

Вход: [8, 2, 6, 5], target=50
Выход: [8], [2], [8, 2], [6], [2, 6], [5], [6, 5]
Пояснение: существует семь подходящих непрерывных подмассивов.

Решение

Используем скользящее окно с двумя указателями. Добавляя arr[right], умножаем на него произведение окна. Пока произведение не меньше цели, делим его на левый элемент и сдвигаем left.

После сжатия произведение всего окна [left, right] меньше цели. Поскольку все числа положительны, подходят и все его суффиксы, заканчивающиеся в right. Добавляем их от самого короткого к самому длинному, чтобы не создавать дубликаты.

Код

package main

import "fmt"

func findSubarrays(arr []int, target int) [][]int {
	result := [][]int{}
	if target <= 1 {
		return result
	}

	product := 1
	left := 0
	for right, value := range arr {
		product *= value
		for product >= target && left <= right {
			product /= arr[left]
			left++
		}

		for start := right; start >= left; start-- {
			subarray := append([]int(nil), arr[start:right+1]...)
			result = append(result, subarray)
		}
	}

	return result
}

func main() {
	fmt.Println(findSubarrays([]int{2, 5, 3, 10}, 30))
	fmt.Println(findSubarrays([]int{8, 2, 6, 5}, 50))
}

Вывод:

[[2] [5] [2 5] [3] [5 3] [10]]
[[8] [2] [8 2] [6] [2 6] [5] [6 5]]

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

Управление окном занимает \(O(N)\) времени: каждый элемент входит в окно и выходит из него не более одного раза. Создание и копирование всех подмассивов в худшем случае занимает \(O(N^3)\) времени.

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

Не считая результата, временный подмассив требует до \(O(N)\) памяти. Число подмассивов может достигать \(N(N+1)/2\), то есть \(O(N^2)\); если учитывать все хранимые в них элементы, полный размер результата достигает \(O(N^3)\).

---