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, recherchez un sous-tableau continu dans le tableau dont la somme correspond à la somme donnée. Le problème peut être divisé en deux variantes principales :

1. Sous-tableau avec 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 
Sortir
Subarray found from index 1 to 3

Analyse

• Complexité temporelle : O(n²) en raison des deux boucles imbriquées itérant dans le tableau.
• Complexité de l'espace : 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 par 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  targetSum && start 
Sortir
Subarray found from index 1 to 3

Analyse

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