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

Методы:

1. Подход грубой силы:
   Подход грубой силы включает в себя проверку всех возможных подмассивов и вычисление их сумм. Хотя этот метод прост, он не самый эффективный. Вот пример того, как это работает:

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

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

def find_subarray_with_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 arr[start:end]
        window_sum += arr[end]
    return None

3. Техника префиксной суммы:
   Техника префиксной суммы полезна, когда данный массив содержит как положительные, так и отрицательные числа. Он предварительно вычисляет сумму всех подмассивов и использует то свойство, что сумма подмассива от индекса i до j может быть рассчитана как prefix_sum[j] – prefix_sum[i-1]. Вот пример:

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

4. Техника двух указателей.
   Техника двух указателей применима, когда массив содержит неотрицательные числа. Он использует два указателя, левый и правый, для управления окном и его настройки на основе суммы. Вот пример:

def find_subarray_with_sum(arr, target_sum):
    n = len(arr)
    left = 0
    right = 0
    curr_sum = arr[0]
    while right < n:
        if curr_sum == target_sum:
            return arr[left:right+1]
        elif curr_sum < target_sum:
            right += 1
            if right < n:
                curr_sum += arr[right]
        else:
            curr_sum -= arr[left]
            left += 1
    return None

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