是否有一个总和为目标的子数组？ [英] Is there a subarray that sums to a target?

问题描述

热门面试问题：

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

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

例如

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

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

推荐答案

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

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

请注意，必须预先检查负目标值以确保循环不变量 i< = j 。具体来说，当 i == j 时， acc 将为 0 ，并且一个正目标可确保 if（符合<目标）下的分支被命中。

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.

这篇关于是否有一个总和为目标的子数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！