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

Постановка задачи

По заданному массиву целых чисел и целевой сумме найдите в массиве непрерывный подмассив, сумма которого равна заданной сумме. Проблему можно разделить на два основных варианта:

1. Подмассив с положительными числами: массив содержит только положительные числа.
2. Подмассив со смешанными числами: массив содержит как положительные, так и отрицательные числа.

Давайте рассмотрим различные методы решения этих вариантов.

Подход 1: использование грубой силы

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

Выполнение

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
Выход
Subarray found from index 1 to 3

Анализ

• Временная сложность: O(n²) из-за двух вложенных циклов, перебирающих массив.
• Пространственная сложность: O(1), поскольку дополнительное пространство за пределами входного массива не используется.

Подход 2: использование скользящего окна

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

Выполнение

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
Выход
Subarray found from index 1 to 3

Анализ

• Временная сложность: O(n), поскольку каждый элемент обрабатывается не более двух раз.
• Пространственная сложность: O(1), поскольку дополнительное пространство не требуется.