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

Метод 1: подход грубой силы
Метод грубой силы включает в себя проверку всех возможных подмассивов и вычисление их сумм. Вот пример реализации на Python:

def find_subarray_sum(arr, target_sum):
    n = len(arr)
    for i in range(n):
        current_sum = arr[i]
        if current_sum == target_sum:
            return [i, i]
        for j in range(i + 1, n):
            current_sum += arr[j]
            if current_sum == target_sum:
                return [i, j]
    return None

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

def find_subarray_sum(arr, target_sum):
    n = len(arr)
    window_sum = arr[0]
    start = 0
    for end in range(1, n):
        while window_sum > target_sum and start < end - 1:
            window_sum -= arr[start]
            start += 1
        if window_sum == target_sum:
            return [start, end - 1]
        window_sum += arr[end]
    return None

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

def find_subarray_sum(arr, target_sum):
    prefix_sum = {0: -1}
    current_sum = 0
    for i, num in enumerate(arr):
        current_sum += num
        if current_sum - target_sum in prefix_sum:
            return [prefix_sum[current_sum - target_sum] + 1, i]
        prefix_sum[current_sum] = i
    return None

Метод 4: подход с двумя указателями
Подход с двумя указателями — еще один эффективный метод поиска подмассива с заданной суммой. Он использует два указателя для сканирования массива и настройки окна на основе текущей суммы. Вот пример реализации:

def find_subarray_sum(arr, target_sum):
    n = len(arr)
    start = 0
    end = 0
    current_sum = 0
    while end < n:
        if current_sum == target_sum:
            return [start, end - 1]
        elif current_sum < target_sum:
            current_sum += arr[end]
            end += 1
        else:
            current_sum -= arr[start]
            start += 1
    return None

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