1. Calculate the sum of every prefix of the array O(n)
2. Store as pairs (sum, index) and sort by sum using a stable sort.
Observation: Sum of every factor can be expressed as the difference
between the sum of 2 prefixes.
3. for each entry search for the corresponding difference such the index
found is greater than original index.
Works for any sum, not just 0. Takes O(n log n)
On 2 September 2012 14:22, Navin Kumar <[email protected]> wrote:
> Given an unsorted integer array. Find the contiguous sub sequences whose
> sum is 0.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/pFvfWQjVrnkJ.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
