# Java 22 ms O(n) beats 100% by minimizing map access

• Even though HashMap operations are amortized O(1) in practice they are not that fast which usually means that things like `if (map.containsKey(...)) {map.get(...)...}` should be avoided. I was coding with that in mind, and got this solution. It was 26 ms first, then I added a termination condition that stopped searching if it is guaranteed that there won't be any better results. That improved to 24 ms. Then I figured out that I can allocate a `HashMap` with a specified capacity—that sped up to 22 ms, and the strange thing is, if I specify capacity equal to `nums.length` instead of `nums.length + 1`, I get 19 ms for some reason. Probably some random subtle effect explained by the specific test cases (such as hash function giving better distribution for certain capacity values).

``````public int maxSubArrayLen(int[] nums, int k) {
int[] sum = new int[nums.length + 1];
Map<Integer, Integer> longest = new HashMap<>(nums.length + 1);
longest.put(0, 0); // The longest sum that equals to 0 so far is the zero-length prefix sum.
for (int i = 0; i < nums.length; ++i) {
sum[i + 1] = sum[i] + nums[i];
longest.put(sum[i + 1], i + 1);
}
int len = 0;
for (int i = 0; i < nums.length; ++i) {
// What is the largest j such as that sum[j] - sum[i] = k?
// It's the same as the largest j such as that sum[j] = k + sum[i].
Integer l = longest.get(k + sum[i]);
if (l != null && l - i > len) {
if (l >= nums.length - 1) {
return l - i; // It doesn't get any longer than this!
} else {
len = l - i;
}
}
}
return len;
}``````

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