6.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

Solution I: (Using Prefix Sum)

class Solution
{
public:
    int subarraySum(vector<int> &nums, int target)
    {

        vector<int> v(nums.size());
        int s = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            s = s + nums[i];
            v[i] = s;
        }

        int k, count = 0, i, j;
        for ( i = 0; i < v.size(); i++)
        {
            for (j = i; j < v.size(); j++)
            {
                if (i == 0)
                {
                    k = v[j];
                }
                else
                {
                    k = v[j] - v[i - 1];
                }
                
              
                if (k == target)
                {
                    count++;
                }
            }
        }

        return count;
    }
};

Time Complexity: O(N^2) , Space Complexity: O(N)

Solution II: (Using Hashmap)

class Solution
{
public:
    int subarraySum(vector<int> &nums, int target)
    {
        unordered_map<int, int> m;
        int preSum = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            preSum = preSum + nums[i];

            if (preSum == target)
            {
                count++;
            }

            if (m.find(preSum - target) != m.end())
            {
                count += m[preSum - target];
            }

            m[preSum]++;
            
        }

        return count;
    }
};

Time Complexity: O(N) , Space Complexity: O(N)

Subarray sum for +ve integer

If a subarray has sum greater than the given sum then there is no possibility that adding elements to the current subarray the sum will be x (given sum). Idea is to use a similar approach to a sliding window. Start with an empty subarray, add elements to the subarray until the sum is less than x. If the sum is greater than x, remove elements from the start of the current subarray.