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 kann in zwei Hauptvarianten unterteilt werden:

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: Einsatz brutaler Gewalt

Der Brute-Force-Ansatz beinhaltet die Überprüfung aller möglichen Unterarrays und die Berechnung ihrer Summen, 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.

Durchführung

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

Analyse

• Zeitkomplexitä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 verkleinert, bis die Summe kleiner oder gleich dem Ziel ist.

Durchführung

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

    for (int end = 0; end  targetSum && start 
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 Raum benötigt wird.