Leetcode 560) Subarray Sum Equals K

29 Sep 2021 in Algorithms

My Answer

class Solution {
    public int subarraySum(int[] nums, int k) {
        for(int  i=1;i<nums.length;i++){
            nums[i]+=nums[i-1];
        }
        Map<Integer,Integer> m = new HashMap<>();

        int cnt =0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==k){
                cnt++;
            }
            if(m.containsKey(nums[i]-k)){
                cnt +=m.get(nums[i]-k);
            }

            if(!m.containsKey(nums[i])){
                m.put(nums[i],1);
            }else{
                m.put(nums[i],m.get(nums[i])+1);
            }
        }
        return cnt;
    }
}

Other Answer

• Instead of using cumulative sum array, It used runningSum variable

class Solution {
    public int subarraySum(int[] nums, int k) {        
        int runningSum = 0;
        int res = 0;
        Map<Integer,Integer> m = new HashMap<>();
        m.put(0,1);

        for(int i=0;i<nums.length;i++){
            runningSum += nums[i];
            int complement = runningSum-k;

            if(m.containsKey(complement)){
                res += m.get(complement);
            }

            if(m.containsKey(runningSum)){
                m.put(runningSum,m.get(runningSum)+1);
            }else{
                m.put(runningSum,1);
            }
        }

        return res;
    }
}