Is there a subarray that sums to a target?

Question

Popular interview question:

Given an array of positive integers and a target integer, find if there is a consecutive subarray that sums to the target.

E.g.

Array = [1,3,6,7,8,10] Target = 16 The subarray that sums to 16 is [3,6,7], so it returns true.

Answer 1

This one goes linear time (C++ code).

bool Test(const int* arr, int size, int target) {
  if (target < 0) return false;
  int acc = 0;
  int i = 0, j = 0;
  while (acc != target) {
    if (acc < target) {
      if (j == size) break;
      acc += arr[j++];
    }
    else {
      acc -= arr[i++];
    }
  }
  return acc == target;
}

Note that the pre-check for a negative target value is necessary to guarantee the loop invariant that i <= j. Specifically, when i == j, acc will be 0, and a positive target guarantees that the branch under if (acc < target) is hit.