Largest Continuous Sequence Zero Sum
Find the largest continuous sequence in a array which sums to zero.
Example:
Input: {1 ,2 ,-2 ,4 ,-4}
Output: {2 ,-2 ,4 ,-4}
NOTE : If there are multiple correct answers, return the sequence which occurs first in the array.
public class Solution {
public int[] lszero(int[] A) {
int maxLen = 0, index = -1, sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < A.length; i++) {
sum = sum + A[i];
if (map.containsKey(sum) || sum == 0) {
int start = -1;
if (map.containsKey(sum))
start = map.get(sum);
int currentLen = i - start;
if (currentLen > maxLen) {
maxLen = currentLen;
index = start + 1;
}
} else {
map.put(sum, i);
}
}
int[] ans = new int[maxLen];
for (int i = index; i < index + maxLen; i++) {
ans[i - index] = A[i];
}
return ans;
}
}
Last updated