Subarray mit gegebener Summe in Java mit verschiedenen Ansätzen

Das Finden eines Subarrays mit einer bestimmten Summe ist ein häufiges Problem, das häufig bei Codierungsinterviews und Wettbewerbsprogrammen auftritt. Dieses Problem kann mit verschiedenen Techniken gelöst werden, von denen jede ihre eigenen Kompromisse hinsichtlich der zeitlichen und räumlichen Komplexität aufweist. In diesem Artikel untersuchen wir mehrere Ansätze zur Lösung des Problems, ein Subarray mit einer bestimmten Summe in Java zu finden.

Problemstellung

Suchen Sie bei einem gegebenen Array von Ganzzahlen und einer Zielsumme ein kontinuierliches Unterarray im Array, das sich zur angegebenen Summe addiert. Das Problem lässt sich in zwei Hauptvarianten unterteilen:

1. Subarray mit positiven Zahlen: Das Array enthält nur positive Zahlen.
2. Subarray mit gemischten Zahlen: Das Array enthält sowohl positive als auch negative Zahlen.

Lassen Sie uns verschiedene Methoden zur Lösung dieser Varianten untersuchen.

Ansatz 1: Brute Force anwenden

Beim Brute-Force-Ansatz werden alle möglichen Unterarrays überprüft und ihre Summen berechnet, um festzustellen, ob einer von ihnen der Zielsumme entspricht. Dieser Ansatz funktioniert für beide Varianten, ist jedoch aufgrund seiner quadratischen Zeitkomplexität für große Arrays ineffizient.

Umsetzung

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start < n; start++) {
      int currentSum = 0;
      for (int end = start; end < n; end++) {
        currentSum += arr[end];
        if (currentSum == targetSum) {
          return new int[] {
            start,
            end
          };
        }
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Ausgabe

Subarray found from index 1 to 3

Analyse

• Zeitliche Komplexität: O(n²) aufgrund der zwei verschachtelten Schleifen, die das Array durchlaufen.
• Raumkomplexität: O(1), da kein zusätzlicher Raum über das Eingabearray hinaus verwendet wird.

Ansatz 2: Schiebefenster verwenden

Der Schiebefenster-Ansatz ist effizient für Arrays, die nur positive Zahlen enthalten. Bei dieser Technik wird ein Fenster mit Elementen verwaltet, die zusammen die Zielsumme ergeben. Das Fenster wird durch Hinzufügen von Elementen erweitert, bis die Summe das Ziel überschreitet, und durch Entfernen von Elementen vom Anfang an verkleinert, bis die Summe kleiner oder gleich dem Ziel ist.

Umsetzung

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

    for (int end = 0; end < arr.length; end++) {
      currentSum += arr[end];

      while (currentSum > targetSum && start < end) {
        currentSum -= arr[start];
        start++;
      }

      if (currentSum == targetSum) {
        return new int[] {
          start,
          end
        };
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Ausgabe

Subarray found from index 1 to 3

Analyse

• Zeitkomplexität: O(n), da jedes Element höchstens zweimal verarbeitet wird.
• Raumkomplexität: O(1), da kein zusätzlicher Platz benötigt wird.

Das obige ist der detaillierte Inhalt vonSubarray mit gegebener Summe in Java mit verschiedenen Ansätzen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!