三个求和为0的最大子数组方法

问题：
设有一个数组 $a[1],a[2],a[3],\ldots,a[n]$
求这个数组的最长子数组，这个子数组元素和为 $0$

例如，对于数组 $\{1,3,8,-11,0,-7,12\}$
其和为 $0$ 的最长子数组为 $\{3,8,-11,0\}$

方法一：

既然所求的是最大子数组，我们不妨从长往短找，以便减少查找次数

对于数组 $a[1],a[2],a[3],\ldots,a[n]$

1. 其最长子数组为其本身，所以先计算
   $$a[1]+a[2]+\cdots+a[n]$$
   判断其是否为 $0$
2. 其次长子数组为 $a[1],a[2]…,a[n-1]$ 和 $a[2],a[3]…,a[n]$
   分别计算这两个子数组和
3. 依次减少数组长度，直到找到最长子数组

需要注意的是：

• 若找到长为k的最长子数组，不能立刻停止计算
  而要继续计算完剩下长度为k的子数组是否和为0，防止最长子数组不唯一
• 分析该种计算方法，在最坏情况下(即最长子数组不存在)，需要的计算步骤为：
  $$1+2+3+\cdots+n=\Theta(n^2)$$
  即时间复杂度是数组长度的平方

这种算法相信是大家都能想到的，思想是“暴力枚举”

那么有没有一种方法可以简化寻找次数呢？

方法二：

对于数组 $a[1],a[2],\ldots,a[n]$ 我们想到：能不能通过分治的方法简化运算呢？

我们可以将 $a[1],a[2],\ldots,a[n]$ 分为 $a[1],a[2],\ldots,a[n/2]$ 和 $a[n/2+1],\ldots,a[n]$ 两个部分
再分别求两部分的和为 $0$的最长子数组
再找到我们刻意忽略的跨过 $a[n/2]$ 和 $a[n/2+1]$ 的最长和为0子数组
最后取较大者

这种计算方法需要以下步骤：

1. 将 $a[1],a[2],\ldots,a[n]$ 分为 $a[1],a[2],\ldots,a[n/2]$ 和 $a[n/2+1],\ldots,a[n]$
2. 找到 $a[1],a[2],\ldots,a[n/2]$ 和 $a[n/2+1],\ldots,a[n]$ 的和为 $0$ 的最长子数组
3. 找到跨过 $a[n/2]$ 和 $a[n/2+1]$ 的最长和为 $0$ 子数组
4. 取最大者

注：

• 若 $n/2$ 仍较大，可继续把 $a[1],a[2],\ldots,a[n/2]$ 再分下去
• 事实上，真正需要计算的只有步骤3，即其实只需要计算如何“合并”即(在此不予证明)
  该种算法时间复杂度比枚举稍有优化，为 $\Theta(n\log n)$

方法3：

还能继续简化计算步骤么？可以的：

如果我们令
$$S_n=a[1]+a[2]+\cdots+a[n]$$
即
$$\begin{align} S_1 &= a[1]\\ S_2 &= a[1]+a[2]\\ S_3 &= a[1]+a[2]+a[3]\\ &\cdots \end{align}$$

那么我们可以得到一个明显的结论：

如果 $S_i = S_j$ ，那么 $a[i+1]+a[i+2]+\cdots+a[j] = 0$

如：
$$S_1=1 \quad S_2=5 \quad S_3=8 \quad S_4=1$$

则 $a[2]+a[3]+a[4]=0$

用这种算法，我们只需要对 $a[n]$ 的数组进行一次加法运算并记录(甚至不需要记录)相同 $S_i$出现的位置
就可以很快的计算出和为 $0$ 的最长子数组