python - 总和等于 0 的最大子数组

Question

这是一个典型的面试问题。给定一个既包含正元素又包含负元素且不为 0 的数组，找到其和等于 0 的最大子数组。我试图解决这个问题。这就是我想出的。

def sub_array_sum(array,k=0):
    start_index = -1
    hash_sum = {}
    current_sum = 0
    keys = set()
    best_index_hash = {}
    for i in array:
        start_index += 1
        current_sum += i
        if current_sum in hash_sum:
            hash_sum[current_sum].append(start_index)
            keys.add(current_sum)
        else:
            if current_sum == 0:
                best_index_hash[start_index] = [(0,start_index)]
            else:
                hash_sum[current_sum] = [start_index]
    if keys:
        for k_1 in keys:
            best_start = hash_sum.get(k_1)[0]
            best_end_list = hash_sum.get(k_1)[1:]
            for best_end in best_end_list:
                if abs(best_start-best_end) in best_index_hash:
                    best_index_hash[abs(best_start-best_end)].append((best_start+1,best_end))
                else:
                    best_index_hash[abs(best_start-best_end)] = [(best_start+1,best_end)]

    if best_index_hash:
        (bs,be) = best_index_hash[max(best_index_hash.keys(),key=int)].pop()
        return array[bs:be+1]
    else:
        print "No sub array with sum equal to 0"


def Main():
    a = [6,-2,8,5,4,-9,8,-2,1,2]
    b = [-8,8]
    c = [-7,8,-1]
    d = [2200,300,-6,6,5,-9]
    e = [-9,9,-6,-3]
    print sub_array_sum(a)
    print sub_array_sum(b)
    print sub_array_sum(c)
    print sub_array_sum(d)
    print sub_array_sum(e)

if __name__ == '__main__':
    Main()

我不确定这是否会满足所有边缘情况。如果有人可以对此发表评论，那就太好了我还想将其扩展为等于任何 K 而不仅仅是 0 的总和。我应该怎么做。任何进一步优化它的建议也很有帮助。

Answer 1

你已经给出了一个很好的线性时间解决方案(比此时其他两个答案更好，它们是二次时间的)，基于每当 sum(i .. j) = 0 时，它必须是sum(0 .. i-1) = sum(0 .. j) 反之亦然。本质上，您计算所有 i 的前缀和 sum(0 .. i)，构建一个哈希表 hash_sum，其中 hash_sum[x] 是 i 拥有的所有位置的列表总和(0 .. i)= x。然后你遍历这个哈希表，一次一个总和，寻找由多个前缀组成的任何总和。在所有此类多次生成的总和中，您选择由一对相距最远的前缀生成的总和 - 这是最长的。

由于您已经注意到使该算法成为线性时间所需的关键洞察力，我对您为什么在第二个循环的 best_index_hash 中建立这么多不必要的东西感到有点困惑。对于给定的总和 x，构成该总和的相距最远的一对前缀将始终是 hash_sum[x] 中的最小和最大条目，它们必然是第一个和最后一个条目(因为那是它们被附加的顺序)，所以不需要循环遍历它们之间的元素。事实上，您甚至根本不需要第二个循环:您可以在第一个循环中保持运行最大值，方法是将 start_index 视为最右边的端点。

要处理任意差异 k:我们需要找到前缀总和为 current_sum 的最左边出现，而不是找到最左边出现的前缀总和 current_sum - k。但这只是 first_with_sum{current_sum - k}。

以下代码未经测试，但应该可以工作:

def sub_array_sum(array,k=0):
    start_index = -1
    first_with_sum = {}
    first_with_sum{0} = -1
    best_start = -1
    best_len = 0
    current_sum = 0
    for i in array:
        start_index += 1
        current_sum += i
        if current_sum - k in first_with_sum:
            if start_index - first_with_sum{current_sum - k} > best_len:
                best_start = first_with_sum{current_sum - k} + 1
                best_len = start_index - first_with_sum{current_sum - k}
        else:
            first_with_sum{current_sum} = start_index

    if best_len > 0:
        return array[best_start:best_start+best_len-1]
    else:
        print "No subarray found"

在开头设置 first_with_sum{0} = -1 意味着我们不必将从索引 0 开始的范围视为特例。请注意，此算法不会改进原始算法的渐近时间或空间复杂度，但它更易于实现，并且在包含零和子数组的任何输入上使用的空间都较少。