Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].


class Solution {
    public int subarraySum(int[] nums, int k) {
       
         int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            int sum = 0;
            for (int j = i; j < nums.length; ++j) {
                sum += nums[j];
                if (sum == k)
                {
                    count++;
                }
            }
        }
        return count;
       
    }
}


Here, take i element and j starts from i continues till end of array and add each element to sum. If it equals to k, then increment count .

Time Complexity: O(n^2)

METHOD 2:


class Solution {
    public int subarraySum(int[] nums, int k) {
       
        HashMap <Integer, Integer> prevSum = new HashMap<>(); 
       
        int result = 0; 

        int currsum = 0; 
       
        for (int i = 0; i < nums.length; i++) { 
       
            currsum += nums[i]; 
       
           
            if (currsum == k)  
                result++;         
       
          
            if (prevSum.containsKey(currsum - k))  
                result += prevSum.get(currsum - k); 
               
            Integer count = prevSum.get(currsum);
            if (count == null)
                prevSum.put(currsum, 1);
            else
                prevSum.put(currsum, count+1); 
        } 
       
        return result; 
       
    }
}


This solution provides less time complexity compared to above solution. Here, we are creating a hash map to store a each subarray currSum with its count. Here, subarray currSum is stored as key and count is stored as value.

1) Add each element to currSum and if it equals to k, then increment result by 1.
2) If currSum is not in a map,then add it to map with count value as sum.
3) If same currSum is found then increments count value. It occurs if array has same numbers. (eg) [0,0,0,0,0,0].
4) If currSum - k (i.e.,currSum greater than k which indicates that it having another subarray sum in currSum (eg) if currSum is 4, k is 2 then it is having another subarray ), then get currSum - k count values and add it count to result.

Time Complexity: O(n)
Space Complexity: O(n)