Searching for a sum of any series in array

Question

I'm given this method, and requested to analyze what it does, and minimize its complexity (both time and space).
All values are known to be larger than zero.

public static boolean search(int[] a, int num) {
    for(int i = 0; i < a.length; i++)
        for(int j = i; j < a.length; j++) {
            int res = 0;
            for(int k = i; k <= j; k++)                
                res += a[k];

            if(res == num) 
                return true;
        }
    return false;
}

From what it looks to me it's searching for any series of consecutive numbers in the given array, that sum up to num, with an O(n³) complexity.

I've tried to rewrite it like this:

public static boolean search(int[] a, int num) {
    for (int i = 0; i < a.length; i++) {
        int sum = 0;
        for (int j = i; j < a.length; j++) {
            sum += a[j];
            if (sum == num) 
                return true;
        }

        if (num > sum)
            break;
    }
    return false;
}

Which has a complexity of (BTW, is there a better way to denote this complexity?).

What other strategies can I take to minimize the complexity even further? Can I reach O(n)?

Answer 1

Both the original and your revision have the same problem. They reset sum/res to zero on every iteration and then recalculate it. To avoid this, store the sums in an array.

int[] sums = new int[a.length + 1];
sums[0] = 0;
for (int i = 0; i < a.length; i++) {
    sums[i + 1] = sums[i] + a[i];
}

This takes \$\mathcal{O}(n)\$ time to calculate.

For any i, sums[i] is the sum of the first i elements of the array.

Since we know that all values are positive, adding a value always increases the sum. And removing a value decreases it. So how do we use that? Consider

int left = 0;
int right = 0;
while (right < sums.length) {
    int sum = sums[right] - sums[left];
    if (sum == target) {
        return true;
    }

    if (sum > target) {
        // if the sum is too big, reduce it by dropping a value from it
        left++;
    } else {
        // if the sum is too small, increase it by adding a value to it
        right++;
    }
}

I changed the name of num to target as being more descriptive of what it represents.

This uses the sums stored in our array to calculate the sum from left + 1 to right in the original array.

On each iteration of the loop, we either return or increment one of the indexes. The worst case is where the sum of the elements before the last is too small but the last element itself is equal to or larger than the target. In that case, we increment right sums.length times and we increment left sums.length times. That's \$2n + 2\$ total, which is \$\mathcal{O}(n)\$.

---

This takes \$\mathcal{O}(n)\$ space as well. If you need constant space, you can skip the first part and track the sum as an integer. See here.

If you can't see the deleted answer from mtj, it basically says to do something like

int left = 0;
int right = 0;
int sum = 0;
while (right < a.length) {
    if (sum > target) {
        // if the sum is too big, reduce it by dropping a value from it
        sum -= a[left];
        left++;
    } else {
        // if the sum is too small, increase it by adding a value to it
        sum += a[right];
        right++;
    }

    if (sum == target) {
        return true;
    }
}

return false;

Assumes that target and all the values in a are positive.

You can see a solution to a similar problem here as well.