Druk alle subarrays af met een som van 0
Probeer het eens op GfG Practice 
Uitvoer
Uitvoer
Gegeven een array arr[] van grootte N de taak is om alle subarrays in de array met som af te drukken .
Voorbeelden:
Invoer: arr = [6 3 -1 -3 4 -2 2 4 6 -12 -7]
Uitgang:
Subarray gevonden van Index 2 tot 4
Subarray gevonden van Index 2 tot 6
Subarray gevonden van Index 5 tot 6
Subarray gevonden van Index 6 tot 9
Subarray gevonden van index 0 tot 10Invoer: arr = [1 2 -3 3 -1 -1]
Uitgang:Subarray gevonden van Index 0 tot 2
Subarray gevonden van Index 2 tot 3
Subarray gevonden van Index 3 tot 5
[Naïeve aanpak] Door alle mogelijke subarrays te genereren - O(n 2 ) tijd en O(1) hulpruimte
C++De basisbenadering is het overwegen alle mogelijke subarrays en controleert of hun som nul is. Hoewel deze aanpak eenvoudig maar inefficiënt is, ook voor grote arrays.
// 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 ); }
Uitvoer
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
Tijdcomplexiteit: OP 2 ) omdat we 2 lussen gebruiken.
Hulpruimte: O(1) omdat er constant extra ruimte nodig is.
[Verwachte aanpak] Gebruiken Hashing - O(n) tijd en O(n) hulpruimte
C++Een efficiëntere aanpak is om hashing te gebruiken om de cumulatieve som van elementen en hun indices op te slaan. Hierdoor kan worden gecontroleerd of er in constante tijd een subarray met een som van nul bestaat.
Hieronder vindt u gedetailleerde stappen van intuïtie:
- Maak een hashkaart om de cumulatieve som en bijbehorende indices op te slaan.
- Initialiseer de cumulatieve som op nul.
- Doorkruis de array:
- Voeg het huidige element toe aan de cumulatieve som.
- Als de cumulatieve som nul is, wordt een subarray vanaf het begin tot aan de huidige index gevonden.
- Als de cumulatieve som al aanwezig is in de hashkaart, betekent dit dat er een subarray is met een som van nul.
- Bewaar de cumulatieve som en index in de hashkaart.
// 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 );
Uitvoer
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
Tijdcomplexiteit: O(n) waarbij n het aantal elementen in de array is.
Hulpruimte: O(n) voor het opslaan van de hashkaart.
