Udskriv alle underordnede med 0 sum
Prøv det på GFG -praksis 
Produktion
Produktion
Givet en matrix arr [] af størrelse n Opgaven er at udskrive alle underordnede i matrixen, der har summen .
Eksempler:
Input: ARR = [6 3 -1 -3 4 -2 2 4 6 -12 -7]
Produktion:Subarray fundet fra indeks 2 til 4
Subarray fundet fra indeks 2 til 6
Subarray fundet fra indeks 5 til 6
Subarray fundet fra indeks 6 til 9
Subarray fundet fra indeks 0 til 10Input: ARR = [1 2 -3 3 -1 -1]
Produktion:Subarray fundet fra indeks 0 til 2
Subarray fundet fra indeks 2 til 3
Subarray fundet fra indeks 3 til 5
[Naiv tilgang] Ved at generere alle mulige undergray - O (n 2 ) tid og o (1) hjælpeplads
C++Den meget basale tilgang er at overveje Alle mulige underordnede og kontrollerer, om deres sum er nul. Selvom denne tilgang er enkel, men ineffektiv også for store 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 ); }
Produktion
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
Tidskompleksitet: PÅ 2 ) Da vi bruger 2 sløjfer.
Hjælprum: O (1) som konstant ekstra plads er påkrævet.
[Forventet tilgang] Brug Hashing - o (n) tid og o (n) hjælpeplads
C++En mere effektiv tilgang er at bruge hashing til at opbevare den kumulative sum af elementer og deres indekser. Dette giver mulighed for at kontrollere, om der findes en underordning med nul sum i konstant tid.
Nedenfor er detaljerede trin i intuition:
- Opret et hash -kort til opbevaring af den kumulative sum og tilsvarende indekser.
- Initialiser den kumulative sum til nul.
- Traverse arrayet:
- Tilføj det aktuelle element til det kumulative sum.
- Hvis den kumulative sum er nul, findes der en undergrad fra begyndelsen til det nuværende indeks.
- Hvis den kumulative sum allerede er til stede på hash -kortet, betyder det, at der er en underarray med nul sum.
- Opbevar den kumulative sum og indeks på hashkortet.
// 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 );
Produktion
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
Tidskompleksitet: O (n) hvor n er antallet af elementer i matrixen.
Hjælprum: O (n) Til opbevaring af hash -kortet.
