So, my friend gave me this exercise and asked me to solve it. Sometimes it’s fun to solve algorithm problem… sometimes…

Given an array A of n integer numbers, find all the (i,j) pairs such that A[i] + A[i+1] + A[i+2] + … + A[j] = 6. For example, A = [1, 5, 4, -2, 4, 8, 7, 9, 0], these pairs are valid i,j (0,1) and (2,4) because sum(A[0->1])=6 and sum(A[2->4])=6

Of course, the worst solution is to perform n² operations. For each number in A, do another loop inside that to find the sub-sequence having the sum = 6.

Surely there should be a better solution. And here is the O(n) solution.

• Loop through A from 0. For each item
  • Calculate the sum(A[0->i]). Remember to use an accumulate variable so that you don’t have to loop again each time.
• Now, perform another loop through A, for each item i, if there exist an j that sum(A[i->j])=6, which means sum(A[0->i]) + 6 = sum(A[0->j]). You job is to look up a value computed before. To do that, use a map to store the result from previous step for O(1) access.

The above solution uses 2 loops but can be considered as O(n). You can optimise it more to use a single loop but the basic idea is still the same.