# AlgoDaily 21: Contiguous Subarray Sum

https://algodaily.com/challenges/contiguous-subarray-sum

There’s a fairly obvious brute-force `O(n^2)`

way to do this by looping through
every possible sub-array:

```
function sum(numbers) {
return numbers.reduce((sum, x) => sum + x, 0);
}
function* allSubArrays(numbers) {
for (let i = 0; i <= numbers.length; i++) {
for (let j = 0; j <= numbers.length; j++) {
const slice = numbers.slice(i, j);
if (slice.length > 0) {
yield slice;
}
}
}
}
function subarraySum(numbers, targetSum) {
for (let sub of allSubArrays(numbers)) {
if (sum(sub) === targetSum) {
return true;
}
}
return false;
}
```

This is `O(n^2)`

, so not great, but I can’t think of a different way to do it.
We could make some small optimisations by skipping a subarray as soon as
possible, but the worst case would still be `O(n^2)`

.

*Algo Daily* has a more efficient solution using a hashmap to cache previously
calculated subarray sums. If we reach a point where the sum minus the target sum
is in the sums cache, we know that it’s possible to make the target sum using a
subarray of the numbers.

```
function subarraySum(numbers, targetSum) {
const seenSums = { 0: true };
let cumulativeSum = 0;
for (let num of numbers) {
cumulativeSum += num;
if (seenSums[cumulativeSum - targetSum]) {
return true;
}
seenSums[cumulativeSum] = true;
}
return false;
}
```

This might be easier to understand with more extreme numbers as the example (often a good trick):

```
subarraySum([100, 3, 4], 7);
```

When we reach the final iteration, the seen sums are
`{"0":true,"100":true,"103":true}`

and the cumulative sum is `103 + 4 = 107`

.

We check if `107 - 7 = 100`

appears in the seen sums, because we can exclude any
irrelevant earlier sums by subtracting the target sum from the whole running
total. As `107 - 7 = 100`

does indeed appear in the seen sums, we know that we
can achieve the target sum with the other numbers.