vector LongestSum0(const vector &A)
{
vector output(2);
unordered_map sumIndexMap;
int n = A.size();
long long sum = 0;
int maxLen = 0;
if (n < 1) return output;
for(int i = 0; i < n; i++) {
sum += A[i];
if (sum == 0) {
maxLen = i + 1;
output[0] = 0;
output[1] = i;
}
else if (sumIndexMap.find(sum) != sumIndexMap.end()) {
if (i - sumIndexMap[sum] + 1 > maxLen) {
maxLen = i - sumIndexMap[sum] + 1;
output[0] = sumIndexMap[sum] ;
output[1] = i;
}
}
else {
sumIndexMap[sum] = i;
}
}
return output;
}
Online Judge Solutions
- Google (1)
- LeetCode Solutions (32)
- LintCode Solutions (68)
- Marked (38)
- Misc. (8)
Thursday, December 11, 2014
Longest sub array with sum equal to zero
Given an array of integers, find the longest continuous sub array which sum equals to zero
Labels:
Google
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment