arrays - 是否有一个总和为目标的子数组？

热门面试问题:

给定一个正整数数组和一个目标整数，找到是否有一个连续的子数组求和。

例如。

数组= [1,3,6,7,8,10]目标= 16总计为16的子数组是[3,6,7]，因此它返回true。

最佳答案

这是线性时间(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 < target)下的分支被命中。

关于arrays - 是否有一个总和为目标的子数组？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32960829/