Programme JavaScript pour savoir s'il existe un sous-tableau dont la somme est égale à 0

En tant que développeurs, on nous demande souvent de trouver s'il existe un sous-tableau dans un tableau dont la somme est égale à 0. Cela peut être fait en utilisant le concept de somme de préfixes. Nous garderons une trace de la somme des éléments du sous-tableau vus jusqu'à présent et la stockerons dans une hashmap. Si la somme a été vue auparavant, alors un sous-tableau avec cette somme existe et la somme est 0. Nous mettrons continuellement à jour la hashmap avec la somme des éléments que nous avons vus jusqu'à présent. De cette façon, nous pouvons déterminer s'il existe un sous-tableau avec une somme de 0 dans le tableau.

Méthode

• Initialisez la variable "sum" à 0 et initialisez l'objet "hash_map" pour stocker la valeur de la somme comme clé et son index comme valeur.

• Parcourez le tableau donné, pour chaque élément -

• Ajoutez l'élément actuel à la somme.

• Renvoie vrai si la somme actuelle est 0 ou existe déjà dans le hash_map, car il existe un sous-tableau avec une somme de 0.

• Sinon, insérez la valeur de la somme et son index dans le hash_map.

• Si la boucle se termine, renvoyez false car il n'y a pas de sous-tableau dont la somme est égale à 0.

• hash_map permet de suivre les sommes cumulées et de déterminer s'il existe des sommes en double.

• Si une somme en double est trouvée, cela signifie qu'il existe un sous-tableau entre les deux sommes avec une somme de 0.

• La complexité temporelle de cette méthode est O(n), où n est le nombre d'éléments dans le tableau donné.

Exemple

Voici un exemple complet de programme JavaScript pour savoir s'il existe un sous-tableau dont la somme est 0 -

function hasZeroSum(arr) {
   let sum = 0;
   let set = new Set();
     
   for (let i = 0; i < arr.length; i++) {
      sum += arr[i];
      if (set.has(sum)) return true;
      set.add(sum);
   }
    
   return false;
}
const arr = [4, 2, -3, 1, 6];
console.log(hasZeroSum(arr));

Instructions

La fonction

• hasZeroSum prend un tableau arr comme argument.

• Nous initialisons deux variables sum et set. La variable sum est utilisée pour suivre la somme actuelle des éléments du sous-tableau, et la variable set est utilisée pour stocker la somme vue précédemment.

  李>

• Ensuite, nous utilisons une boucle for pour parcourir les éléments du tableau.

• À chaque itération, nous ajoutons l'élément actuel à sum et vérifions si set contient déjà la valeur de sum.

• Si la valeur de sum est déjà dans le set, signifie que la somme des sous-tableaux depuis la première occurrence de cette somme jusqu'à la fin de l'élément actuel est 0, donc nous retournons true.

• Si la valeur de sum n'est pas dans le set, nous l'ajoutons à l'ensemble.

• Si nous parcourons l'ensemble du tableau et ne renvoyons pas true, cela signifie qu'il n'y a pas de sous-tableau dont la somme est égale à 0, donc nous renvoyons false.

• Enfin, nous testons la fonction à l'aide de l'exemple de tableau et enregistrons les résultats sur la console.

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!