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

Методы поиска подмассивов с заданной суммой:

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

   def find_subarrays_brute_force(arr, target_sum):
   n = len(arr)
   for i in range(n):
       current_sum = arr[i]
       if current_sum == target_sum:
           print(f"Subarray found at index [{i}]")
       for j in range(i + 1, n):
           current_sum += arr[j]
           if current_sum == target_sum:
               print(f"Subarray found from index [{i+1}] to [{j}]")
               break

2. Использование суммы префиксов.
   Этот метод использует концепцию суммы префиксов для эффективного поиска подмассивов с нужной суммой. Поддерживая совокупную сумму элементов до заданного индекса, мы можем определить сумму любого подмассива за постоянное время.

   def find_subarrays_prefix_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:
           start = prefix_sum[current_sum - target_sum] + 1
           print(f"Subarray found from index [{start}] to [{i}]")
       prefix_sum[current_sum] = i

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

   def find_subarrays_sliding_window(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:
           print(f"Subarray found from index [{start}] to [{end-1}]")
       window_sum += arr[end]
   if window_sum == target_sum:
       print(f"Subarray found from index [{start}] to [{n-1}]")

4. Использование хеширования.
   Этот метод использует хеш-таблицу для хранения совокупной суммы элементов, обнаруженных на данный момент. Проверив, существует ли в хеш-таблице разница между текущей суммой и целевой суммой, мы можем определить наличие подмассивов с нужной суммой.

   def find_subarrays_hashing(arr, target_sum):
   sum_map = {0: -1}
   current_sum = 0
   for i, num in enumerate(arr):
       current_sum += num
       if current_sum - target_sum in sum_map:
           start = sum_map[current_sum - target_sum] + 1
           print(f"Subarray found from index [{start}] to [{i}]")
       sum_map[current_sum] = i