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

Question

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

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

输出=1,8（1是起始索引，8是最后索引）

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

Answer 1

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

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

只要返回值为true，您就可以检查覆盖的间隔是否比目前遇到的大。

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]));