在 O(nlogn) 时间复杂度（使用分而治之）中找到和为 0 的子数组？

Question

我在网上看过解决方案，但所有解决方案的时间复杂度都是 O(n) 或 O(n^2)。我想知道是否有可能在不使用辅助数据结构的 O(nlogn) 中找到和为 0 的子数组。但是，我们可以使用递归。

我们可以修改最大子数组和算法来找到这个问题的解吗？

输入数组将只有 1 和 -1，算法将找到和为 0 的子数组。

输入 = { 1, 1, -1, 1, -1, -1, 1, -1}

output = 1, 8（1 是起始索引，8 是最后一个索引）

在这种特殊情况下，整个输入数组的总和等于 0。因此，报告的起始和结束索引分别为 1 和 8（假设数组中的索引从 1 开始）。

编辑：我们可以使用这个问题的解决方案来解决另一个问题。该问题如下。

给定一个包含n个整数的数组arr，找到偶数元素和奇数元素数量相等的最长连续子数组。下面是一个示例（索引从 1 开始）：

A = {8, 2, -3, 4, 9, 6}

答案：（2、5）。（2 是起始索引，5 是最后一个索引）

唯一的限制是该算法不能使用任何辅助数据结构。在此约束下，解决方案必须是最有效的。此外，允许使用递归。

Answer 1

您可以使用递归算法，其中函数获取前一个数组值（如果有）的值，然后从输入数组中读取下一个值。如果它是相同的值，那么它递归地调用自己，当从那里返回时，它以相同的方式继续下一个值。如果它是相反的值，它 return 将发送给调用者 true -- 以指示总和为零。如果遇到数组末尾，函数returns false.

这实际上意味着递归的深度等于绝对累加和。因此，例如，如果数组是 [-1, -1, -1, 1]，那么递归将进入深度 3，并且它将 return 从 level 3 到 level 2 with return值 true。在级别 2 它将 return false 因为遇到了数组的末尾，所以它会退出递归。

每当 return 值为 true 时，您可以检查覆盖区间的大小是否大于目前遇到的区间大小。

下面是这个想法在 JavaScript 中的实现：

function zeroSum(arr) {
  let i = 0; // index in the input array, managed outside of recursion
  // Longest zero-sum interval so far. Zero based, and value at end index 
  //   is not part of the interval:
  let longest = [0, 0];

  function recur(dir) { // dir is the previous value from the array (if any)
    let start = i; // local variable
    while (i < arr.length) {
      let val = arr[i++];
      if (val == -dir) return true; // zero sum
      if (recur(val) && i - start > longest[1] - longest[0]) {
        longest[0] = start;
        longest[1] = i;
      }
    }
    return false; // no zero sum
  }

  recur(0); // 0 is passed to indicate there is no previous value
  return longest;
}

// demo
console.log(zeroSum([1, 1, -1, 1, -1, -1, 1, -1]));

在 O(nlogn) 时间复杂度（使用分而治之）中找到和为 0 的子数组？

Find a subarray with sum 0 in O(nlogn) time complexity (Using Divide and Conquer)?

algorithm

divide-and-conquer