Vytlačte všetky čiastkové sumy s 0 sumou
Vyskúšajte to v praxi GFG 
Výstup
Výstup
Vzhľadom na pole ARR [] veľkosť n Úlohou je vytlačiť všetky čiastky v poli, ktorý má sumu .
Príklady:
Vstup: ARR = [6 3 -1 -3 4 -2 2 4 6 -12 -7]
Výstup:
Podpary nájdený z indexu 2 až 4
Podpary nájdený z indexu 2 až 6
Podpary nájdený z indexu 5 až 6
Podpary nájdený z indexu 6 až 9
Podpary nájdený z indexu 0 až 10Vstup: ARR = [1 2 -3 3 -1 -1]
Výstup:Podpary nájdený z indexu 0 až 2
Podpary nájdený z indexu 2 až 3
Podpary nájdený z indexu 3 až 5
[Naivný prístup] generovaním všetkých možných podskupín - O (n 2 ) čas a O (1) pomocný priestor
C++Samotným základným prístupom je zvážiť Všetky možné čiastky a kontroluje, či je ich suma nula. Aj keď je tento prístup jednoduchý, ale neefektívny aj pre veľké polia.
// 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 ); }
Výstup
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
Časová zložitosť: O (n 2 ) Pretože používame 2 slučky.
Pomocný priestor: O (1), pretože je potrebný konštantný priestor navyše.
[Očakávaný prístup] pomocou Hashovanie - O (n) čas a O (n) pomocný priestor
C++Efektívnejším prístupom je použitie hashovania na ukladanie kumulatívneho súčtu prvkov a ich indexov. To umožňuje skontrolovať, či v konštantnom čase existuje podprúd s nulovým sumou.
Nižšie sú uvedené podrobné kroky intuície:
- Vytvorte hashovú mapu na uloženie kumulatívneho súčtu a zodpovedajúcich indexov.
- Inicializujte kumulatívny súčet na nulu.
- Prejdite pole:
- Pridajte aktuálny prvok k kumulatívnej súčtu.
- Ak je kumulatívny súčet nula nula, zistí sa podprúd od začiatku do aktuálneho indexu.
- Ak je kumulatívna suma už prítomná v hashovej mape, znamená to, že existuje čiastka s nulovým súčtom.
- Uložte kumulatívny súčet a index do hashovej mapy.
// 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 );
Výstup
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
Časová zložitosť: O (n) kde n je počet prvkov v poli.
Pomocný priestor: O (n) na uloženie hashovej mapy.
