Blogs Hub

by Sumit Chourasia | Nov 21, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Subarray Sum Equals K - Array - Medium - LeetCode

Subarray Sum Equals K - Array - Medium - LeetCode

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

 

Example 1:

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

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

Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        var map = new Dictionary<int,int>();
        map.Add(0,1);
        int sum = 0;
        int res = 0;
        for(int i=0;i<nums.Length;i++){
            sum += nums[i];
            int count = 0;
            map.TryGetValue(sum-k, out count);
            res+=count;
            
            int val=0;
            map.TryGetValue(sum, out val);
            map[sum]=val+1;
        }
        
        return res;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)