Problem Statement #
Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.
Example 1:
Input: [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].
Subarray Sum Equals K - Brute Force Approach:
var subarraySum = function (nums, k) {
let n = nums.length;
let count = 0;
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n; j++) {
// Calculate required sum
sum += nums[j];
// Check if sum is equal to
// required sum
if (sum == k) count++;
}
}
return count;
};
2) Using Map / HasMap:
Above logic works on principal of prefix sum array or cumulative sum array.
If SUM - K exist in hasMap that means somehow some combination of previous item can give us sum = k;
Equation will be like
currSum - k = Val (this val value is one which can be derived from previous combination)
var subarraySum = function (nums, k) {
const obj = {};
let res = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == k) res++;
if (obj[sum - k]) res += obj[sum - k];
obj[sum] ? (obj[sum] += 1) : (obj[sum] = 1);
}
return res;
};