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


  • 4

    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;
    }

Log in to reply
 

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