# Java O(n), like other subarray sum problem

• There is a variety of subarray sum problem utilize similar technology:

[325] Maximum Size Subarray Sum equal K
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/?tab=Description

We can first calculate array prefix sum, then the problem is convert to
finding presum[j] - presum[i] == target where j - i is maximized.

The above equation can borrow O(n) two sum solution, which use hashmap to store target + presum[i].

Another trick applied in this problem is, when calculating prefix sum, we add -1 instead of 0, when nums[i] == 0. With this trick , we can formulate problem as presum[j] - presum[i] == 0.

``````public int findMaxLength(int[] nums) {
if (nums == null || nums.length <= 1) return 0;
int len = nums.length;

// Store the
Map<Integer, Integer> map = new HashMap<>();
map.put(0,0);
int res = 0;

// Calculate the prefix on the fly.
int sum = 0;

for (int i = 1; i <=len; i++ ) {
sum = sum + (nums[i-1] == 0 ? -1 : 1);
if (map.containsKey(sum)) {
res = Math.max(i - map.get(sum), res);
} else {
map.put(sum, i);
}
}

return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.