logo

TechCodeview

Imprimer tous les sous-tableaux avec une somme de 0

Essayez-le sur GfG Practice ' title=

Étant donné un tableau arr[] de taille n la tâche consiste à imprimer tous les sous-tableaux du tableau qui a une somme .

Exemples :  



liste de tableaux triée

Saisir: arr = [6 3 -1 -3 4 -2 2 4 6 -12 -7]
Sortir:

Sous-tableau trouvé de l'index 2 à 4
Sous-tableau trouvé de l'index 2 à 6
Sous-tableau trouvé de l'index 5 à 6
Sous-tableau trouvé de l'index 6 à 9
Sous-tableau trouvé de l'index 0 à 10

Saisir: arr = [1 2 -3 3 -1 -1]
Sortir:



Sous-tableau trouvé de l'index 0 à 2
Sous-tableau trouvé de l'index 2 à 3
Sous-tableau trouvé de l'index 3 à 5

[Approche naïve] En générant tous les sous-tableaux possibles - O(n2) temps et espace auxiliaire O(1)

L'approche la plus fondamentale consiste à considérer tous les sous-tableaux possibles et vérifie si leur somme est nulle. Bien que cette approche soit simple mais inefficace également pour les grands tableaux.

C++ 
// C++ program to print all subarrays // in the array which has sum 0 #include    using namespace std; vector<pair<int int> > findSubArrays(int arr[] int n) {  // Array to store all the start and end  // indices of subarrays with 0 sum  vector<pair<int int> > output;  for (int i = 0; i < n; i++) {  int prefix = 0;  for (int j = i; j < n; j++) {  prefix += arr[j];  if (prefix == 0)  output.push_back({ i j });  }  }  return output; } // Function to print all subarrays with 0 sum void print(vector<pair<int int> > output) {  for (auto it = output.begin(); it != output.end(); it++)  cout << 'Subarray found from Index ' << it->first  << ' to ' << it->second << endl; } // Driver code int main() {  // Given array  int arr[] = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  vector<pair<int int> > output = findSubArrays(arr n);  // if we didn’t find any subarray with 0 sum  // then subarray doesn’t exists  if (output.size() == 0) {  cout << 'No subarray exists';  }  else {  print(output);  }  return 0; }
Java 
// Java program to print all subarrays // in the array which has sum 0 import java.io.*; import java.util.*; // User defined pair class class Pair {  int first second;  Pair(int a int b)  {  first = a;  second = b;  } } public class GFG {  static ArrayList<Pair> findSubArrays(int[] arr int n)  {  // Array to store all the start and end  // indices of subarrays with 0 sum  ArrayList<Pair> out = new ArrayList<>();  for (int i = 0; i < n; i++) {  int prefix = 0;  for (int j = i; j < n; j++) {  prefix += arr[j];  if (prefix == 0)  out.add(new Pair(i j));  }  }  return out;  }  // Function to print all subarrays with 0 sum  static void print(ArrayList<Pair> out)  {  for (int i = 0; i < out.size(); i++) {  Pair p = out.get(i);  System.out.println('Subarray found from Index '  + p.first + ' to '  + p.second);  }  }  // Driver code  public static void main(String args[])  {  // Given array  int[] arr  = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = arr.length;  // Function Call  ArrayList<Pair> out = findSubArrays(arr n);  // if we didn’t find any subarray with 0 sum  // then subarray doesn’t exists  if (out.size() == 0)  System.out.println('No subarray exists');  else  print(out);  } }
Python 
# User defined pair class class Pair: first = 0 second = 0 def __init__(self a b): self.first = a self.second = b class GFG: @staticmethod def findSubArrays(arr n): # Array to store all the start and end # indices of subarrays with 0 sum out = [] i = 0 while (i < n): prefix = 0 j = i while (j < n): prefix += arr[j] if (prefix == 0): out.append(Pair(i j)) j += 1 i += 1 return out # Function to print all subarrays with 0 sum @staticmethod def print(out): i = 0 while (i < len(out)): p = out[i] print('Subarray found from Index ' + str(p.first) + ' to ' + str(p.second)) i += 1 # Driver code @staticmethod def main(args): # Given array arr = [6 3 -1 -3 4 -2 2 4 6 -12 -7] n = len(arr) # Function Call out = GFG.findSubArrays(arr n) # if we didn't find any subarray with 0 sum # then subarray doesn't exists if (len(out) == 0): print('No subarray exists') else: GFG.print(out) if __name__ == '__main__': GFG.main([])
C# 
using System; using System.Collections.Generic; class GFG {    // Array to store all the start and end  // indices of subarrays with 0 sum  static List<Tuple<int int>> findSubArrays(int[] arr int n)  {  var output = new List<Tuple<int int>>();  for (int i = 0; i < n; i++)  {  int prefix = 0;  for (int j = i; j < n; j++)  {  prefix += arr[j];  if (prefix == 0)  output.Add(Tuple.Create(i j));  }  }  return output;  }  // Function to print all subarrays with 0 sum  static void print(List<Tuple<int int>> output)  {  foreach (var subArray in output)  Console.Write('Subarray found from Index ' + subArray.Item1 + ' to ' + subArray.Item2+'n');  }  // Driver code  public static void Main()  {  // Given array  int[] arr = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = arr.Length;  // Function Call  List<Tuple<int int>> output = findSubArrays(arr n);  // if we didn’t find any subarray with 0 sum  // then subarray doesn’t exists  if (output.Count == 0)  {  Console.WriteLine('No subarray exists');  }  else  {  print(output);  }  } }
JavaScript 
// Javascript program to print all subarrays // in the array which has sum 0 function findSubArrays(arr n) {  // Array to store all the start and end  // indices of subarrays with 0 sum  let out =[];  for (let i = 0; i < n; i++) {  let prefix = 0;  for (let j = i; j < n; j++) {  prefix += arr[j];  if (prefix == 0)  out.push([i j]);  }  }  return out; } // Function to print all subarrays with 0 sum function print(out) {  for (let it of out)  console.log('Subarray found from Index ' + it[0]  + ' to ' + it[1]); } // Driver code // Given array let arr = [ 6 3 -1 -3 4 -2 2 4 6 -12 -7 ]; let n = arr.length ; // Function Call let out = findSubArrays(arr n); // if we didn’t find any subarray with 0 sum // then subarray doesn’t exists if (out.length == 0) {  console.log('No subarray exists'); } else {  print(out); }

Sortir 
Subarray found from Index 0 to 10 Subarray found from Index 2 to 4 Subarray found from Index 2 to 6 Subarray found from Index 5 to 6 Subarray found from Index 6 to 9

Complexité temporelle : SUR2) puisque nous utilisons 2 boucles.
Espace auxiliaire : O(1) car un espace supplémentaire constant est requis.



java synchroniser

[Approche attendue] Utilisation Hachage - O(n) temps et O(n) espace auxiliaire

Une approche plus efficace consiste à utiliser le hachage pour stocker la somme cumulée des éléments et leurs indices. Cela permet de vérifier si un sous-tableau à somme nulle existe en temps constant.

Vous trouverez ci-dessous les étapes détaillées de l'intuition :

  1. Créez une carte de hachage pour stocker la somme cumulée et les indices correspondants.
  2. Initialisez la somme cumulée à zéro.
  3. Parcourez le tableau :
    • Ajoutez l'élément actuel à la somme cumulée.
    • Si la somme cumulée est nulle, un sous-tableau depuis le début jusqu'à l'index actuel est trouvé.
    • Si la somme cumulée est déjà présente dans la carte de hachage, cela signifie qu'il existe un sous-tableau à somme nulle.
    • Stockez la somme cumulée et l'index dans la carte de hachage.
C++ 
// C++ program to print all subarrays // in the array which has sum 0 #include    using namespace std; // Function to print all subarrays in the array which // has sum 0 vector<pair<int int> > findSubArrays(int arr[] int n) {  // create an empty map  unordered_map<int vector<int> > map;  // create an empty vector of pairs to store  // subarray starting and ending index  vector<pair<int int> > out;  // Maintains sum of elements so far  int sum = 0;  for (int i = 0; i < n; i++) {  // add current element to sum  sum += arr[i];  // if sum is 0 we found a subarray starting  // from index 0 and ending at index i  if (sum == 0)  out.push_back(make_pair(0 i));  // If sum already exists in the map there exists  // at-least one subarray ending at index i with  // 0 sum  if (map.find(sum) != map.end()) {  // map[sum] stores starting index of all  // subarrays  vector<int> vc = map[sum];  for (auto it = vc.begin(); it != vc.end(); it++)  out.push_back(make_pair(*it + 1 i));  }  // Important - no else  map[sum].push_back(i);  }  // return output vector  return out; } // Utility function to print all subarrays with sum 0 void print(vector<pair<int int> > out) {  for (auto it = out.begin(); it != out.end(); it++)  cout << 'Subarray found from Index ' << it->first  << ' to ' << it->second << endl; } // Driver code int main() {  int arr[] = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = sizeof(arr) / sizeof(arr[0]);  vector<pair<int int> > out = findSubArrays(arr n);  // if we didn’t find any subarray with 0 sum  // then subarray doesn’t exists  if (out.size() == 0)  cout << 'No subarray exists';  else  print(out);  return 0; }
Java 
// Java program to print all subarrays // in the array which has sum 0 import java.io.*; import java.util.*; // User defined pair class class Pair {  int first second;  Pair(int a int b)  {  first = a;  second = b;  } } public class GFG {  // Function to print all subarrays in the array which  // has sum 0  static ArrayList<Pair> findSubArrays(int[] arr int n)  {  // create an empty map  HashMap<Integer ArrayList<Integer> > map  = new HashMap<>();  // create an empty vector of pairs to store  // subarray starting and ending index  ArrayList<Pair> out = new ArrayList<>();  // Maintains sum of elements so far  int sum = 0;  for (int i = 0; i < n; i++) {  // add current element to sum  sum += arr[i];  // if sum is 0 we found a subarray starting  // from index 0 and ending at index i  if (sum == 0)  out.add(new Pair(0 i));  ArrayList<Integer> al = new ArrayList<>();  // If sum already exists in the map there exists  // at-least one subarray ending at index i with  // 0 sum  if (map.containsKey(sum)) {  // map[sum] stores starting index of all  // subarrays  al = map.get(sum);  for (int it = 0; it < al.size(); it++) {  out.add(new Pair(al.get(it) + 1 i));  }  }  al.add(i);  map.put(sum al);  }  return out;  }  // Utility function to print all subarrays with sum 0  static void print(ArrayList<Pair> out)  {  for (int i = 0; i < out.size(); i++) {  Pair p = out.get(i);  System.out.println('Subarray found from Index '  + p.first + ' to '  + p.second);  }  }  // Driver code  public static void main(String args[])  {  int[] arr  = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = arr.length;  ArrayList<Pair> out = findSubArrays(arr n);  // if we did not find any subarray with 0 sum  // then subarray does not exists  if (out.size() == 0)  System.out.println('No subarray exists');  else  print(out);  } }
Python 
# Python3 program to print all subarrays # in the array which has sum 0 # Function to get all subarrays # in the array which has sum 0 def findSubArrays(arr n): # create a python dict hashMap = {} # create a python list # equivalent to ArrayList out = [] # tracker for sum of elements sum1 = 0 for i in range(n): # increment sum by element of array sum1 += arr[i] # if sum is 0 we found a subarray starting # from index 0 and ending at index i if sum1 == 0: out.append((0 i)) al = [] # If sum already exists in the map # there exists at-least one subarray # ending at index i with 0 sum if sum1 in hashMap: # map[sum] stores starting index # of all subarrays al = hashMap.get(sum1) for it in range(len(al)): out.append((al[it] + 1 i)) al.append(i) hashMap[sum1] = al return out # Utility function to print # all subarrays with sum 0 def printOutput(output): for i in output: print('Subarray found from Index ' + str(i[0]) + ' to ' + str(i[1])) # Driver Code if __name__ == '__main__': arr = [6 3 -1 -3 4 -2 2 4 6 -12 -7] n = len(arr) out = findSubArrays(arr n) # if we did not find any subarray with 0 sum # then subarray does not exists if (len(out) == 0): print('No subarray exists') else: printOutput(out)
C# 
// C# program to print all subarrays // in the array which has sum 0 using System; using System.Collections.Generic; // User defined pair class class Pair {  public int first second;  public Pair(int a int b)  {  first = a;  second = b;  } } class GFG {  // Function to print all subarrays  // in the array which has sum 0  static List<Pair> findSubArrays(int[] arr int n)  {  // create an empty map  Dictionary<int List<int> > map  = new Dictionary<int List<int> >();  // create an empty vector of pairs to store  // subarray starting and ending index  List<Pair> outt = new List<Pair>();  // Maintains sum of elements so far  int sum = 0;  for (int i = 0; i < n; i++) {  // add current element to sum  sum += arr[i];  // if sum is 0 we found a subarray starting  // from index 0 and ending at index i  if (sum == 0)  outt.Add(new Pair(0 i));  List<int> al = new List<int>();  // If sum already exists in the map there exists  // at-least one subarray ending at index i with  // 0 sum  if (map.ContainsKey(sum)) {  // map[sum] stores starting index  // of all subarrays  al = map[sum];  for (int it = 0; it < al.Count; it++) {  outt.Add(new Pair(al[it] + 1 i));  }  }  al.Add(i);  if (map.ContainsKey(sum))  map[sum] = al;  else  map.Add(sum al);  }  return outt;  }  // Utility function to print all subarrays with sum 0  static void print(List<Pair> outt)  {  for (int i = 0; i < outt.Count; i++) {  Pair p = outt[i];  Console.WriteLine('Subarray found from Index '  + p.first + ' to '  + p.second);  }  }  // Driver code  public static void Main(String[] args)  {  int[] arr  = { 6 3 -1 -3 4 -2 2 4 6 -12 -7 };  int n = arr.Length;  List<Pair> outt = findSubArrays(arr n);  // if we did not find any subarray with 0 sum  // then subarray does not exists  if (outt.Count == 0)  Console.WriteLine('No subarray exists');  else  print(outt);  } }
JavaScript 
// JavaScript program to print all subarrays // in the array which has sum 0 // Function to print all subarrays in the array which // has sum 0 function findSubArrays(arr n) {  // create an empty map  let map = {};    // create an empty vector of pairs to store  // subarray starting and ending index  let out = [];    // Maintains sum of elements so far  let sum = 0;    for (var i = 0; i < n; i++)  {  // add current element to sum  sum += arr[i];    // if sum is 0 we found a subarray starting  // from index 0 and ending at index i  if (sum == 0)  out.push([0 i]);    // If sum already exists in the map there exists  // at-least one subarray ending at index i with  // 0 sum  if (map.hasOwnProperty(sum))  {  // map[sum] stores starting index of all subarrays  let vc = map[sum];  for (let it of vc)  out.push([it + 1 i]);  }  else  map[sum] = [];    // Important - no else  map[sum].push(i);  }    // return output vector  return out; }   // Utility function to print all subarrays with sum 0 function print(out) {  for (let it of out)  console.log('Subarray found from Index ' + it[0] + ' to ' + it[1]); }     // Driver code let arr = [6 3 -1 -3 4 -2 2 4 6 -12 -7]; let n = arr.length;   let out = findSubArrays(arr n);   // if we didn’t find any subarray with 0 sum // then subarray doesn’t exists if (out.length == 0)  console.log('No subarray exists'); else  print(out);

Sortir 
Subarray found from Index 2 to 4 Subarray found from Index 2 to 6 Subarray found from Index 5 to 6 Subarray found from Index 6 to 9 Subarray found from Index 0 to 10

Complexité temporelle : O(n) où n est le nombre d'éléments dans le tableau.
Espace auxiliaire : O(n) pour stocker la carte de hachage.