# Java O(n) explain how I come up with this idea

• The subarray sum reminds me the range sum problem. Preprocess the input array such that you get
the range sum in constant time.
sum[i] means the sum from 0 to i inclusively
the sum from i to j is sum[j] - sum[i - 1] except that from 0 to j is sum[j].

j-i is equal to the length of subarray of original array. we want to find the max(j - i)
for any sum[j] we need to find if there is a previous sum[i] such that sum[j] - sum[i] = k
Instead of scanning from 0 to j -1 to find such i, we use hashmap to do the job in constant time.
However, there might be duplicate value of of sum[i] we should avoid overriding its index as we want the max j - i, so we want to keep i as left as possible.

``````public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0)
return 0;
int n = nums.length;
for (int i = 1; i < n; i++)
nums[i] += nums[i - 1];
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // add this fake entry to make sum from 0 to j consistent
int max = 0;
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i] - k))
max = Math.max(max, i - map.get(nums[i] - k));
if (!map.containsKey(nums[i])) // keep only 1st duplicate as we want first index as left as possible
map.put(nums[i], i);
}
return max;
}
}``````

• OMG this is so smaaaaart!! Thank you you are a life saver today!!!!!

• mine is a litter similar, but no extra space for storing sums array and only loops once.
public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int max = 0;
HashMap<Integer, Integer> hm = new HashMap<>();
int prevSum = 0;
hm.put(0, -1);
for (int i = 1; i <= nums.length; i++) {
prevSum += nums[i - 1];
Integer smallIndex = hm.get(prevSum - k);
if (smallIndex != null) {
max = Math.max(i - 1 - smallIndex, max);
}
if (!hm.containsKey(prevSum)) {
hm.put(prevSum, i - 1);
}
}
return max;
}
}

• add this fake entry to make sum from 0 to j consistent

It would be grateful to get more details about the reasons of "map.put(0, -1);"

• @yu-chai1993-outlook-com
if k is the sum of element from nums[0] to nums[i], the len of subarray is i - 0 + 1.
in other words, (0, -1) is the initial status.

• @yu-chai1993-outlook-com look at this part max = Math.max(max, i - map.get(nums[i] - k));
so make map.put(0,-1) is just to say if the nums[i]-k==0 which means index from 0 to index i will make to sum k.
in this case, the length of the subarray will be 0,1,2,...i, which is i+1, so you need the value of map.get(nums[i]-k) to be "-1"

• @xuyirui Lovely. Thanks for explaining how you thought through the solution.

• Same idea but only one loop is needed:

``````public static int maxSubArrayLen(int[] nums, int k) {
int index = -1,sum = 0,maxsize = 0;
HashMap<Integer,Integer> sum_index = new HashMap<Integer,Integer>();
sum_index.put(0,index);
while(++index<nums.length){
sum+=nums[index];
Integer presumIndex = sum_index.get(sum-k);
if(presumIndex!=null&&maxsize<index-presumIndex) maxsize = index-presumIndex;
sum_index.put(sum,sum_index.getOrDefault(sum, index));
}
return maxsize;
}``````

• @NikoBellic thanks! get it!!

• @yliang thank you! really clear!

• ``````public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0)
return 0;
int n = nums.length;
for (int i = 1; i < n; i++)
nums[i] += nums[i - 1];
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);  ------------> map.put(k, -1);

int max = 0;
for (int i = 0; i < n; i++) {
// if (map.containsKey(nums[i] - k))
// why I can't use ?
if(k==sum)
max = Math.max(max, i - map.get(nums[i] - k));---->
max = Math.max(max, i - map.get(k));
if (!map.containsKey(nums[i]))
map.put(nums[i], i);
}
return max;
}
}``````

• Thanks for the smart solution! the "sum[j] - sum[i] = k" helps a lot in my understanding!

And I also find that in the last for loop, the sequence of adding nums[i] to the map and finding if there is nums[i]-k in the map doesn't matter -- adding nums[i] into the map can always be the first task in every loop.

Thanks!

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