是否存在一个子数组，其元素之和等于给定目标值？

Question

流行的面试问题：

给定一个正整数数组和一个目标整数，找出是否存在连续的子数组其总和等于目标值。

例如：

数组 = [1,3,6,7,8,10] 目标值 = 16 总和等于16的子数组是[3,6,7]，因此返回true。

- Akash Magoon

---

请查看下面给出的答案，谢谢。 - Tim Biegeleisen

等一下...你想用什么编程语言？ - Tim Biegeleisen

任何语言都可以。更多的是逻辑。@TimBiegeleisen，你的答案很有道理，看起来也能工作。就复杂度而言，这似乎是O(N^2)。有没有办法让它更有效率？ - Akash Magoon

我没意识到你已经回答了自己的问题 :-) 你可以尝试在 O（NlgN） 时间内对数组进行排序，但我没有看到任何排好序的数组有帮助的地方。 - Tim Biegeleisen

一个线性时间算法应该能够胜任这项工作。 - Lingxi

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 < target)下的分支被触发。

- Lingxi

---

@TonyD 我不这么认为。它假设数组中的整数是正数，就像问题描述中所述的那样。 - Lingxi

看起来它错误地处理了target=0....你说“正目标”，但检查的是非负数..... - gen-y-s

当 target 为 0 时，while 循环根本不会进入，且返回 acc == target（即 true）。因此，目标值为 0 时始终返回 true。当我们将空子数组的和视为 0 时，这应该是正确的。 - Lingxi

Answer 2

刚刚编写并完全测试。有两种方法：hasConsec（其中大部分逻辑）和sumArr（辅助方法，用于对数组中的值求和）。 hasConsec使用2个索引，第一个和最后一个创建子数组。使用helper方法对创建的子数组进行求和，然后hasConsec检查它是否与目标匹配，如果大于目标，则返回true；如果小于目标，则增加最后一个索引；如果大于目标，则增加第一个索引。重复此过程直到第一个索引等于数组的长度。如果发生这种情况，则没有子数组的总和等于目标。返回false;

public static boolean hasConsec(int arr[], int target) {
    int first = 0, last = 0;

    while (last <  arr.length) {
        int sub[] = Arrays.copyOfRange(arr, first, last);
        int subSum = sumArr(sub);
        if (subSum == target) 
             return true;
        else if (subSum < target)
             last++;
        else {
            if (++first < last)
                last = first;
         }
     }
    return false;
}

public static int sumArr(int arr[]) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) 
        sum += arr[i];
     return sum;
 }

- Akash Magoon