AlgoDaily - Contiguous Subarray Sum

Contiguous Subarray Sum (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Splunk, Uber, Coursera, Symantec, Two Sigma, Sap, Hashicorp, Procore, Freshworks, Segment, Carta, Invision, Appdirect, Automattic, Digitalocean, Weave, Veeva Systems, and Mcafee.

Given an array of numbers, return true if there is a subarray that sums up to a certain number n.

A subarray is a contiguous subset of the array. For example the subarray of [1,2,3,4,5] is [1,2,3] or [3,4,5] or [2,3,4] etc.

JAVASCRIPT

1const arr = [1, 2, 3], sum = 5
2subarraySum(arr, sum)
3// true
4// [2, 3] sum up to 5
5
6const arr = [11, 21, 4], sum = 9
7subarraySum(arr, sum)
8// false
9// no subarrays sums up to 9

In the above examples, [2, 3] sum up to 5 so we return true. On the other hand, no subarray in [11, 21, 4] can sum up to 9.

Can you create a function subarraySum that accomplishes this?

Constraints

Length of the array <= 100000
The values in the array will be between 0 and 1000000000
The target sum n will be between 0 and 1000000000
The array can be empty
Expected time complexity : O(n)
Expected space complexity : O(n)

xxxxxxxxxx
​
 
var assert = require('assert');
​
function subarraySum(nums, n) {
  // hash of prefix sums
​
  // Fill in this method
  return nums;
}
​
const arr = [1, 2, 3],
  sum = 5;
console.log(subarraySum(arr, sum));
​
try {
  assert.equal(subarraySum([1, 2, 3], 3), true);
​
  console.log('PASSED: ' + 'assert.equal(subarraySum([ 1, 2, 3 ], 3), true)');
} catch (err) {
  console.log(err);
}
​
try {
  assert.equal(subarraySum([], 3), false);
​
  console.log('PASSED: ' + 'assert.equal(subarraySum([], 3), false)');
} catch (err) {
  console.log(err);

OUTPUT

Results will appear here.