simple JAVA solution Hashmap with only one traverse


  • 0
    C
    public int subarraySum(int[] nums, int k) {
            HashMap<Integer,Integer> hash = new HashMap<>();
            int res=0,sum=0;
            for(int i:nums){
                if(hash.containsKey(sum-k)){
                    res+=hash.get(sum-k);
                }
                hash.put(sum, hash.containsKey(sum) ? hash.get(sum) + 1 : 1);
                sum+=i;
            }
            if(hash.containsKey(sum-k)){
                res+=hash.get(sum-k);
            }
            return res;
        }
    

    this is my solution.

            public int subarraySum(int[] nums, int k) {
            int n = nums.length;
            int[] sum = new int[n + 1];
            for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + nums[i];
            Map<Integer, Integer> map = new HashMap<>();
            int count = 0;
            for (int num : sum) {
                if (map.containsKey(num)) {
                    count += map.get(num);
                }
                map.put(num + k, map.containsKey(num + k) ? map.get(num + k) + 1 : 1);
            }
            return count;
        }
    

    '
    This is another fast code I copied from the run time graph. (Sorry, I do not know who I should thank for this code)
    Although my code does work, I have a question here.
    The code I copied from the graph beats 99%, while mine only about 60%-80%. However, Second code surely does more job than mine who traverses the array twice. Can anybody help me here?


Log in to reply
 

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