Tüm alt dizileri toplam 0 ile yazdır
GfG Practice'de deneyin 
Çıkış
Çıkış
Bir dizi verildiğinde varış[] boyutta N .
Örnekler:
Giriş: sıra = [6 3 -1 -3 4 -2 2 4 6 -12 -7]
Çıkış:Dizin 2'den 4'e kadar bulunan alt dizi
Dizin 2'den 6'ya kadar bulunan alt dizi
Dizin 5'ten 6'ya kadar bulunan alt dizi
Dizin 6'dan 9'a kadar bulunan alt dizi
Dizin 0'dan 10'a kadar bulunan alt diziGiriş: dizi = [1 2 -3 3 -1 -1]
Çıkış:Dizin 0'dan 2'ye kadar bulunan alt dizi
Dizin 2'den 3'e kadar bulunan alt dizi
Dizin 3'ten 5'e kadar bulunan alt dizi
2 ) zaman ve O(1) yardımcı uzay
C++En temel yaklaşım şu: tüm olası alt diziler ve toplamlarının sıfır olup olmadığını kontrol eder. Although this approach is simple but inefficient also for large 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 ); }
Çıkış
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
Zaman Karmaşıklığı: AÇIK 2 ) çünkü 2 döngü kullanıyoruz.
Yardımcı Alan: O(1) sürekli ekstra alan gerektirdiğinden.
[Beklenen Yaklaşım] Kullanımı karma - O(n) zamanı ve O(n) yardımcı uzayı
C++Daha verimli bir yaklaşım, öğelerin ve bunların endekslerinin kümülatif toplamını depolamak için karma kullanmaktır. Bu, sabit zamanda sıfır toplamlı bir alt dizinin var olup olmadığının kontrol edilmesine olanak tanır.
Aşağıda sezginin ayrıntılı adımları verilmiştir:
- Kümülatif toplamı ve karşılık gelen endeksleri depolamak için bir karma haritası oluşturun.
- Kümülatif toplamı sıfıra sıfırlayın.
- Diziyi çaprazlayın:
- Geçerli öğeyi kümülatif toplama ekleyin.
- Kümülatif toplam sıfırsa, başlangıçtan geçerli dizine kadar bir alt dizi bulunur.
- Kümülatif toplam karma haritasında zaten mevcutsa, sıfır toplamlı bir alt dizi olduğu anlamına gelir.
- Kümülatif toplamı ve dizini karma haritasında saklayın.
// 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 );
Çıkış
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
Zaman Karmaşıklığı: O(n) burada n, dizideki öğelerin sayısıdır.
Yardımcı Alan: Karma haritasını saklamak için O(n).
