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

Метод 1: перебор
Подход перебора включает в себя проверку всех возможных подмассивов и поиск подмассива с минимальной суммой. Хотя этот метод прост, его временная сложность составляет O(n^2), что делает его неэффективным для больших массивов. Вот пример реализации на Python:

def min_size_subarray_sum_brute(arr, target):
    min_length = float('inf')
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            subarray_sum = sum(arr[i:j+1])
            if subarray_sum >= target:
                min_length = min(min_length, j - i + 1)
    return min_length if min_length != float('inf') else -1

Метод 2: техника скользящего окна
Техника скользящего окна — это оптимизированный подход для поиска подмассивов с определенной суммой. Он поддерживает два указателя, startи end, которые представляют границы окна. Окно расширяется, когда сумма меньше целевой, и сжимается, когда сумма превышает целевую. Вот пример реализации на Python:

def min_size_subarray_sum_sliding_window(arr, target):
    start = 0
    min_length = float('inf')
    current_sum = 0
    for end in range(len(arr)):
        current_sum += arr[end]
        while current_sum >= target:
            min_length = min(min_length, end - start + 1)
            current_sum -= arr[start]
            start += 1
    return min_length if min_length != float('inf') else -1

Метод 3: сумма префиксов
Техника суммы префиксов предполагает создание вспомогательного массива, где каждый элемент представляет собой сумму всех элементов до этого индекса. Используя этот массив, мы можем вычислить сумму любого подмассива за постоянное время. Вот пример реализации на Python:

def min_size_subarray_sum_prefix_sum(arr, target):
    prefix_sum = [0] * (len(arr) + 1)
    for i in range(1, len(prefix_sum)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
    min_length = float('inf')
    for i in range(len(arr)):
        for j in range(i + 1, len(arr) + 1):
            subarray_sum = prefix_sum[j] - prefix_sum[i]
            if subarray_sum >= target:
                min_length = min(min_length, j - i)
    return min_length if min_length != float('inf') else -1

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

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