Yes Neha, I Never Said That SubArray has to be Started from 0th index,else
What Will be the advantage of this saying subarray anyways, here O(N) time &
O(N) space solution
int prefix_sum = 0;
hash_map<int,int> find_subarray;
int start_index = -1, end_index = -1;
for (int i = 0,;i < n; ++i)
{
if (a[i]==k)
{
start_index = i;
end_index = i;
break;
}
prefix_sum += a[i];
if (prefix_sum==k)
{
start_index = 0;
end_index = i;
break;
}
if (find_subarray.find(prefix_sum) == k)
{
find_subarray[prefix_sum] = i;
}
else
{
start_index = find_subarray[prefix_sum] + 1;
end_index = i;
break;
}
}
if (start_index != -1)
{
cout << "Zero sum subarray found. Start index : " << start_index
<< ". End Index: " << end_index << "\n";
}
-2 1 -2 5 -1 4 -6 -7 k=9 subarray will be -2 5-1 4 -6
@all Whats Say ?
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
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/-/SNpbdnf1PTMJ.
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.
