560. Subarray Sum Equals K - JS

Description

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

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

Solution 1: brute force

Time complexity: O(n^3)

Try all the the possibilities for startIndex and endIndex of subarray, and check the sum to see if equals k

• startIndex: i = 0 ... n
• endIndex: j = i ... n
• sum and check: another loop

---

let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    for( let i = 0; i < n; i++ ){
        for( let j = i; j < n; j++ ){
            let sum = 0;
            for( let k = i; k <= j; k++ ){
                sum += nums[k];
            }
            if(sum === k) cnt++;
        }
    }
    return cnt;
};

Solution 2: optimize using prefix sum

Time complexity: O(n^2)

1. prefixSum array: Spcae Complexity: O(n)

   For the inner most loop, there are duplicate work for the addition to get sum(i, j). In fact, we can process it beforehand, getting an prefix sum array; Then sum(i,j) will be prefixSum[j]-prefixSum[i-1], using O(1) time

2. do summation in the fly: Spcae Complexity: O(1)

// approach #1: prefixSum array
let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    let prefixSum = [];
    prefixSum.push(0);
    for( let i = 0; i < n; i++ ){
        prefixSum[i+1] = prefixSum[i] + nums[i];
    }
    
    for( let i = 0; i < n; i++ ){
        for( let j = i; j < n; j++ ){
            let sum = prefixSum[j+1] - prefixSum[i];
            if(sum === k) cnt++;
        }
    }
    return cnt;
};


// approach #2: do summation in the fly:
let subarraySum = function(nums, k) {
    let cnt = 0;
    let n = nums.length;
    for( let i = 0; i < n; i++ ){
        let sum = 0;
        for( let j = i; j < n; j++ ){
            sum += nums[j];
            if(sum === k) cnt++;
        }
    }
    return cnt;
};

Solution 3: optimize using HashMap

Time complexity: O(n)

Space complexity: O(1)

Based on Solution 2, we can get the subarray sum in O(n), but still the overall time complexity is O(n^2), that’s because we need to try all the possibilities of the startIndex and endIndex of subarray.

For each startIndex: i, the reason we need to iterate endIndex: j is that we want to find all the possible pair to make the subarray sum equals k.

If we change a direction to think about it, why not directly find all the the prefixSum[i'], making prefixSum[j] - prefixSum[i'] = k, and then we count all the possible i'. Thus, we need a memory to let know who will be the counterpart for the current prefixSum[j]. That’s hashmap~

let subarraySum = function(nums, k) {
    let cnt = 0;
    let map = new Map();
    map.set(0, 1); // we use map to store prefixSum values: special case sum=0 in begin
    
    let sum = 0;
    for( let i = 0; i < nums.length; i++ ){
        sum += nums[i];
        let target = sum - k;
        if(map.has(target)) cnt += map.get(target);
        if(!map.has(sum)) map.set(sum, 0);
        map.set(sum, map.get(sum)+1);
    }
    return cnt;
};