是否有一个子数组求和到一个目标？

Question

热门面试问题：

例如。

Array=[1,3,6,7,8,10]Target=16加到16的子数组是[3,6,7]，因此返回true。

Answer 1

这个是线性时间(C++代码）。

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;
}

注意，为了保证i<=j的循环不变量，必须对负目标值进行预检查。具体地说，当I==J时，acc将为0，正目标保证命中IF(acc 下的分支。