[Facebook Question] Subarray Sum Equals K

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

Example:

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

Approach: We can calculate cumulative sum of the array and also we can maintain a hashmap with key as sum and value as number of times key sum occurred while calculating cumulative sum.

Now the solution is just to look for cumulative sum - k in our hashmap and if it is there just add its count to the result.

That's all!

Implementation in C#:

        public int SubarraySum(int[] nums, int k)

        {

            Dictionary<int, int> hash = new Dictionary<int, int>();

            int count = 0, sum = 0;

            hash[0] = 1;

            for (int i = 0; i < nums.Length; ++i)

            {

                sum += nums[i];

                if (hash.ContainsKey(sum - k))

                {

                    count += hash[sum - k];

                }

                if (!hash.ContainsKey(sum))

                {

                    hash[sum] = 0;

                }

                ++hash[sum];

            }

            return count;

        }

Complexity: O(n)