移除顶部或底部两桩等高桩的算法

Question

假设你有两堆，每一堆都是由不同高度的N盒子组成的。你想要移除盒子，以获得两堆等高(如果可能的话)。你不能移除不在堆的顶部或底部的盒子！例如，人们可以看到，如果我们移除下面的红色盒子，我们就会得到两座高度相等的塔：

​

​

另一种表述这个问题的方法是:给定两个正数数组，是否有两个连续的子序列(每个数组中有一个)和相等？

这个问题看起来类似于this one，其中我们有一个大小为N的数组A和一个目标t，我们希望找到一个连续的A子序列，其和是t (等价地，我们有一堆盒子，我们希望删除顶部和底部的框，以获得一堆高度t)。这个问题可以在时间O(N)中得到解决。另一方面，上面提到的问题有一个平凡的O(N^2)解决方案(见下面的答案)，但是是否也有一个o(N^2)算法(例如O(N log N))？

附录:方框的大小是正整数。假设它们都是不同的(否则问题可以在O(N)中解决)。如果我们用H表示两个桩的总大小，就有一个O(H log H)算法(见下面的答案)。因此，这个问题对H来说比N更有趣(为H = N^2提供一个有效的解决方案将是一个好的开端)；

Answer 1

让我们查找O(n^2)中的所有和，并将它们添加到哈希表中：

for l in [0, n)
    cur_sum = 0
    for r in [l, n)
         cur_sum += a[r]
         hash_table.add(cur_sum)

在此之后，我们需要对第二个数组执行相同的操作，并检查哈希表中是否至少出现了一个和。

这比简单的O(n^3)解决方案要好得多。

在O(H log H)时间也可以解决这个问题，如果所有高度都是整数，则H是盒的高度之和，但只有在总高度有限的情况下才有用。

O(H log H)解决方案如下所示：

我们可以快速找到所有子数组和。让我们看一看子数组S和是什么。这是两个前缀和P[r] - P[l] = S的区别。如果把H加到方程的两边，就可以得到P[r] + (H - P[l]) = H + S。因此，我们需要检查数组P[i]和H - P[i]中是否存在两个元素，它们加在一起等于一个给定的值。让我们不仅检查它们的存在，还算出这类对的数量。不，它看上去完全像两个多项式的乘法。第一个多项式的系数是特定前缀和(C[i] = count(j: P[j] == i))出现的次数。第二次多项式本质上是相反的。我们可以用傅里叶快速变换在O(H log H)时间内对这两个多项式进行相乘(因为它们都是H度的)。然后，我们只需要检查乘积的H + i系数是非零的.

一旦我们知道第一个和第二个数组的所有和，我们需要检查它们是否至少有一个共同点。

Answer 2

这听起来类似于查找字符串中最长回文长度的算法。在回文算法中，检查字符串的开始和结束，以确定回文是否存在，如果不存在，则从字符串中删除字符串的第一个字符，以便将字符串的其余部分与去掉字符串的最后一个字符的结果进行比较。

在这种情况下，您正在寻找一个盒子，结果从顶部和底部的堆。如果该桩在另一桩中没有形成相同大小的盒子，则将其顶部取下，并将其与取桩底部的结果进行比较。递归伪码看起来可能类似于：

global pile2
global HashTableForPile2  # each value is a box in Pile2
def FindBoxInPile(pile, top, bottom):
    if (top == ReachedBottomInPile or bottom == ReachedTopInPile):
        Stop processing and return False  ## base case
    else:
        # find the box created from the top to the bottom
        for i in range(bottom, top)
            sumPile1 += pile[i]
        # Determine if an identical box is inside both piles.  
        # If so, return True; otherwise, recurse.
        # (assuming HashTableForPile2 was calculated earlier)
        if (sumPile1 == HashTableForPile2[sumPile1]):  
            return True           

    # take top AND bottom off pile
    if (FindBoxInPile(pile1, top-1, bottom+1) == True):
        return True  # A box is inside both piles

    # take top OR bottom off pile and compare result
    elif (FindBoxInPile(pile1, top-1, bottom) == True or
          FindBoxInPile(pile1, top, bottom+1) == True)
        return True  # A box is inside both piles, return True

动态规划解决方案将在O(N)时间内运行。