O(n) super clean 9-line Java solution with HashMap


  • 121
    H
    public int maxSubArrayLen(int[] nums, int k) {
        int sum = 0, max = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
            if (sum == k) max = i + 1;
            else if (map.containsKey(sum - k)) max = Math.max(max, i - map.get(sum - k));
            if (!map.containsKey(sum)) map.put(sum, i);
        }
        return max;
    }
    

    The HashMap stores the sum of all elements before index i as key, and i as value. For each i, check not only the current sum but also (currentSum - previousSum) to see if there is any that equals k, and update max length.

    PS: An "else" is added. Thanks to beckychiu1988 for comment.


  • 2
    B

    Nice solution! Only one question, if sum == k, we do not need to check the second one cause i+1 must be larger, right? So,
    if (sum == k) max = i + 1;
    else if (map.containsKey(sum - k)) max = Math.max(max, i - map.get(sum - k));


  • 0
    H

    Yes you are right! I should add an "else" to jump over. Thanks.


  • 0
    L
    This post is deleted!

  • -6
    Z

    are u sure this is O(n) solution? cause the hash map method - containsKey() will always consume time which is related to the array. In worst case, i think it is not O(n).


  • 0
    H

    On average it's o(1). Please see this: http://stackoverflow.com/questions/8923251/what-is-the-time-complexity-of-hashmap-containskey-in-java

    I think the worst case rarely happens. Thanks for pointing out anyway.


  • 1
    Z

    My bad. Thank you!


  • 19
    2

    Same 9 lines of code, but put the special case from 0 to i int the HashMap.
    Cleaner logic in the loop.

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

  • 0
    G

    very nice solution. I like the "hm.put(0,-1)"


  • 0

    Very good solution!


  • 0
    X

    Nice solution!


  • 0

    Very nice solution! HashMap is so useful in many places.
    Maybe we could use new feature and API of JDK to make it more concise.
    Not sure if it is accepted. Just for your reference.

        public int maxSubArrayLen(int[] nums, int k) {
            Map<Integer, Integer> seen = new HashMap<>();
            int max = 0;
            for (int i = 0, sum = 0; i < nums.length; i++) {
                sum += nums[i];
                if (sum == k) max = i + 1; /* i+1 must be longest by now, so no need to max() */
                else max = Math.max(max, i - seen.getOrDefault(sum - k, i)); /* [0,j]=sum-k, (j,i]=k */
                seen.putIfAbsent(sum, i);
            }
            return max;
        }
    

  • 0
    C

    This is a very nice solution, thank you.


  • 0
    J
    This post is deleted!

  • 0
    M

    @he17 So how about if we meet the same sum again but that may result in a larger max. Don't we need to update the value belonging to the key?


  • 0
    P

    @morphling2 you never need to update keys here. As you can see, Your key - is sum of elements from 0 to i. It's static.
    The idea here that if sum(0,i) - sum(0,j) equals k, it means that sum(i,j) equals k. And (i-j) is a length of a subsequence, that's what we care about, that's what we store to max and update when needed.


  • 0
    E

    @he17 I think this solution is not working for all test cases

    For example, [-1,10,7,-2,5] in order to find 5(sum), the result should return 0 but it returns 2. What do you think?


  • 0
    E

    @he17 Sorry my bad, I have seen that "nums array is guaranteed to fit within the 32-bit signed integer range."


  • 0
    This post is deleted!

Log in to reply