Java HashTable Solution beats 99.77%


  • 2
    H
    public class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            if(nums.length==0) return 0;
            if(nums.length==1){
                if(nums[0]==k) return 1;
                return 0;
            }
            int[] sum = new int[nums.length+1];
            sum[0] = 0;
            for(int i=1;i<sum.length;i++){
                sum[i] = sum[i-1] + nums[i-1];
            }
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
            for(int i=0;i<sum.length;i++){
                hashtable.put(sum[i], i);
            }
            int max = 0;
            for(int i=0;i<sum.length;i++){
                Integer c = hashtable.get(sum[i]+k);
                if(c != null && c.intValue() > i && c.intValue() - i > max)
                    max = c.intValue() - i;
            }
            return max;
        }
    }

  • 0
    R

    Can anybody explain me why this is much faster than

    public class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            int sum = 0, max = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            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;
        }
    }
    

    OP solution introduced more for 2 more for loops yet end up being faster. Both of the solution is O(n).


  • 0
    J

    @ratchapong.t Difference is constant. You have 2 if clause in loop, so it is 2n, which is larger than OP's. Since clauses like 'Integer c = hashtable.get(sum[i]+k);' does not take time.


  • 0
    E

    Why do you use

    c.intValue()
    

    Instead of simply c since it is already an Integer the comparison should work.
    I removed the .intValue() and the solution still works and it's actually faster.


Log in to reply
 

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