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

Метод 1: подход грубой силы
Самый простой подход к решению этой проблемы — использование алгоритма грубой силы. Перебираем все возможные подмассивы и вычисляем их сумму. Если сумма соответствует K, мы возвращаем подмассив.

def subarray_with_k_sum(arr, K):
    n = len(arr)
    for i in range(n):
        curr_sum = 0
        for j in range(i, n):
            curr_sum += arr[j]
            if curr_sum == K:
                return arr[i:j+1]
    return None

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

def subarray_with_k_sum(arr, K):
    n = len(arr)
    sum_map = {}
    curr_sum = 0
    for i in range(n):
        curr_sum += arr[i]
        if curr_sum == K:
            return arr[:i+1]
        if curr_sum - K in sum_map:
            return arr[sum_map[curr_sum - K]+1:i+1]
        sum_map[curr_sum] = i
    return None

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

def subarray_with_k_sum(arr, K):
    n = len(arr)
    left = 0
    curr_sum = 0
    for right in range(n):
        curr_sum += arr[right]
        while curr_sum > K:
            curr_sum -= arr[left]
            left += 1
        if curr_sum == K:
            return arr[left:right+1]
    return None

Метод 4: метод префиксной суммы
Метод префиксной суммы включает в себя вычисление совокупной суммы элементов до каждого индекса. Сохранив эти суммы в массиве, мы можем легко определить сумму любого подмассива.

def subarray_with_k_sum(arr, K):
    prefix_sum = [0]
    for num in arr:
        prefix_sum.append(prefix_sum[-1] + num)
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n+1):
            if prefix_sum[j] - prefix_sum[i] == K:
                return arr[i:j]
    return None

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