create another array with sum of the elements from 0 to i. 20 , -9 , 3 , 1, 5 , 0, -6 , 9 20 , 11,14,15,20,0,14,23 above thing can be done in O(n) .
now start hashing them (sum as keys and index as value), and if the sum exist previously , then that means from that point , from where you are hashing to the point of the value of previously hashed key , the Sum is 0. store all the index at that sum . use something like this map(int , vector <int> >; . I guess you are getting my point , if not , please free feel to ping. Oveall comlexity is nlog(n) . n -no of elements and log n is searching time in hash maps.... On Wed, Jul 20, 2011 at 6:47 PM, Pankaj <jatka.oppimi...@gmail.com> wrote: > Given an array with + and - numbers, including zero, Write an algorithm to > find all the possible sub arrays which sum up to zero. > > For example, if given array is > > 20 , -9 , 3 , 1, 5 , 0, -6 , 9 > > Then possible sub arrays are: > -9, 3, 1, 5 > 0 > 1, 5, 0, -6 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
