找到最大跨度 (i,j) 的最快算法，使得 , ai + ai+1 +....+aj = bi +数组 a 和 b 中的 bi+1 +....+bj

Question

我在准备考试时遇到了这个问题。

给定两个数字数组 a1,..., an 和 b1,....,bn，其中每个数字都是 0 或 1，找到最大跨度 (i,j) 的最快算法，使得 , ai + ai+1 +....+aj = bi + bi+1 +....+bj 或报告不存在这样的跨度。

(A) 如果允许散列，则需要 O(3^n) 和 omega(2^n) 时间。

(B) 在密钥比较模式下需要 O(n^3) 和 omega(n^2.5) 和时间

(C) 需要 theta(n) 时间和空间

(D) 仅需要 O(square-root(n)) 时间如果2n个元素的和是偶数。

Answer 1

这是一个 O(n) 算法，

l=[1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1,1,1,0]
m=[0,0,0,0,1,0,1,1,1,0,0,0,1,1,1,0,0,0,1]
delta=[]
for i in range(0,len(l)):
    delta.append(l[i]-m[i])

leftsum=[0]
for i in range(1,len(l)+1):
    leftsum.append(leftsum[i-1]+delta[i-1])

sumHash=[-1]*len(l)

maxLen=0;
leftIndex=-1
rightIndex=-1

for i in range(0,len(l)+1):
    if sumHash[leftsum[i]]!=-1:
        if maxLen<i-sumHash[leftsum[i]]:
            maxLen=i-sumHash[leftsum[i]]
            leftIndex=sumHash[leftsum[i]]
            rightIndex=i-1
    else:
        sumHash[leftsum[i]]=i

print 'len=',maxLen,'left=',leftIndex,'right=',rightIndex

Answer 2

如果有人愿意做正确的检查，我能想到的唯一解决方案是 O(n^2) 和 omega(n) 时间。如果有人设法找到一种方法来利用所有 0 和 1 的值，那么它可能会得到改进。

int[] a = { 1, 1, 0, 1, 1, 0, 1, 0, 1 };
int[] b = { 0, 1, 0, 0, 1, 1, 0, 1, 0 };

int lastSum = 0; int lastI = 0; int lastJ = 0;
int sumA = 0; int sumB = 0; 
for(int i = 0; i < a.Length; i++) // start the sum at [i].
{
    sumA = a[i]; sumB = b[i];
    for (int j = i + 1; j < a.Length; j++) // summing ends on [j]
    //do
    {
        if (sumA == sumB && (lastJ - lastI < j - i))
        {
            lastSum = sumA;
            lastI = i; lastJ = j;
            if (j == a.Length - 1) // you will never find a bigger interval.
            {
                Console.Out.WriteLine("(i, j) = (" + lastI + ", " + lastJ + ")");
                return;
            }
        }
        sumA += a[j];
        sumB += b[j];
    }
}
Console.Out.WriteLine("(i, j) = (" + lastI + ", " + lastJ + ")");

Answer 3

该问题可以在θ(n)时间和空间内得到解决。

1. 由于总共有 n 个元素，因此最大和为 n
   对于两个数组。
2. 总和差值从 -n 到 n 不等。所以总共有 2n+1 个可能的值。
3. 如果 2 个数组的两个前缀和之差在两个点处相同，则 2 个点之间的子数组具有相同的和。

算法：

1. 创建一个大小为2n+1的辅助数组来存储所有可能的差值的起点。
2. 将所有差异的起始值初始化为-1。
3. maxlen = 0;presum1=0;presum2=0;(2个数组的前缀和)
4. for( int i=0;i>n;i++){
   1. preSum1 += arr1[i], preSum2 += arr2[i];
   2. curr_diff = preSum1 - PreSum2;
   3. diffIndex = n + curr_diff {curr_diff(-n 到 n)
   4. 如果 curr_diff 为 0 ，则 maxlen = i+1；
   5. 否则，如果第一次看到 curr_diff，则开始
      curr_diff 的点为-1，更新起始点为 i
   6. 否则，则将 i 视为当前相同和跨度的端点和最终长度。如果长度大于则更新 maxlen
5. 返回 maxlen