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