Online Judge Solutions

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
 

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;
}

No comments:

Post a Comment