Sous-tableau avec une somme donnée en Java avec différentes approches

Trouver un sous-tableau avec une somme donnée est un problème courant qui apparaît souvent lors des entretiens de codage et de la programmation compétitive. Ce problème peut être résolu à l’aide de diverses techniques, chacune avec ses propres compromis en termes de complexité temporelle et spatiale. Dans cet article, nous explorerons plusieurs approches pour résoudre le problème de la recherche d'un sous-tableau avec une somme donnée en Java.

Énoncé du problème

Étant donné un tableau d'entiers et une somme cible, trouvez un sous-tableau continu dans le tableau qui totalise la somme donnée. Le problème peut être divisé en deux variantes principales :

1. Sous-tableau avec des nombres positifs : le tableau ne contient que des nombres positifs.
2. Sous-tableau avec nombres mixtes : le tableau contient à la fois des nombres positifs et négatifs.

Explorons différentes méthodes pour résoudre ces variantes.

Approche 1 : Utiliser la force brute

L'approche par force brute consiste à vérifier tous les sous-tableaux possibles et à calculer leurs sommes pour voir si l'un d'entre eux est égal à la somme cible. Cette approche fonctionne pour les deux variantes mais est inefficace pour les grands tableaux en raison de sa complexité temporelle quadratique.

Mise en œuvre

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.");
    }
  }
}

Sortie

Subarray found from index 1 to 3

Analyse

• Complexité temporelle : O(n²) en raison des deux boucles imbriquées parcourant le tableau.
• Complexité spatiale : O(1) car aucun espace supplémentaire n'est utilisé au-delà du tableau d'entrée.

Approche 2 : Utilisation de la fenêtre coulissante

L'approche de la fenêtre glissante est efficace pour les tableaux contenant uniquement des nombres positifs. Cette technique consiste à maintenir une fenêtre d'éléments qui totalisent la somme cible. La fenêtre est agrandie en ajoutant des éléments jusqu'à ce que la somme dépasse l'objectif, et réduite en supprimant des éléments depuis le début jusqu'à ce que la somme soit inférieure ou égale à l'objectif.

Mise en œuvre

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.");
    }
  }
}

Sortie

Subarray found from index 1 to 3

Analyse

• Complexité temporelle : O(n) car chaque élément est traité au plus deux fois.
• Complexité spatiale : O(1) puisqu'aucun espace supplémentaire n'est nécessaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!