三个求和为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 \) 的最长子数组

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注