# Concise Java Code with explanation(Prefix Trick)

• Pre:

1. any subarray could be a subarray from 0 to j MINUS subarray from 0 to i (i < j);

2. prefix[i] denotes the subarray from 0 to i(exclusively), so it will consider prefix[0] as empty subarray

Now let's explain this question:

*1. if we met a 0, we minus 1, met 1, plus 1. Let's record it for every position int the prefix sum, and call it 0/1sum.

*2. we want to find all the subarray(which is also denotes by position: 0 ~ position(exclusively)) whose 0/1sum are same.
Actually we only want to remember the first position, so when we get last position we could get the longest length.

*3. so we use HashMap to record the position of the every different 0/1sum when it first appear, let's say it's "i". and when we met other same 0/1sum with different position "j", we subtract j - i to get the length. Maintain a “max” to record the max length, return it in the end.](link url)

``````class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int[] prefix = new int[nums.length + 1];
map.put(0, 0);
int max = 0;
for (int i = 1; i < prefix.length; i++) {
prefix[i] = prefix[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
if (map.containsKey(prefix[i])) {
max = Math.max(max, i - map.get(prefix[i]));
}
if (!map.containsKey(prefix[i])) {
map.put(prefix[i], i);
}
}
return max;
}
}
``````

Together with LC 325, Framework

``````class Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int[] prefix = new int[nums.length + 1];
map.put(0, 0);
int max = 0;
for (int i = 1; i < prefix.length; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
if (map.containsKey(prefix[i] - k)) {
max = Math.max(max, i - map.get(prefix[i] - k));
}
if (!map.containsKey(prefix[i])) {
map.put(prefix[i], i);
}
}
return max;
}
}
``````

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