这是一个典型的面试问题。给定一个包含正负元素且不含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。我该怎么做呢。任何进一步优化这一点的指针也很有帮助。在
我同意sundar nataraj的观点,他说这必须发布到代码评审论坛。在
尽管我看了你的代码。虽然我能够理解您的方法,但我无法理解使用
Counter
的必要性。在best_index_hash[start_index] = [(0,start_index)]
-这里best_index_hash
属于Counter
类型。你为什么要给它分配一个列表?for key_1, value_1 in best_index_hash.most_common(1)
-您试图得到largest
子序列,为此,您使用most_common
作为答案。这不是直观的语义。我很想发布一个解决方案,但我会等你编辑代码片段并加以改进。在
附录
为了好玩,我尝试了这个拼图,我在下面展示了我的努力。我不保证正确性/完整性。在
这是我自己的答案,只是为了好玩。在
子序列的数量是二次的,并且子序列求和的时间是线性的,所以最朴素的解应该是立方的。在
这种方法只是对子序列进行彻底的搜索,但是有点小技巧避免了线性求和因子,所以它只是二次型的。在
你给出了一个很好的线性时间解(比现在的两个答案更好,都是二次时间),基于这样一个思想:无论何时求和(i。。j) =0,必须是该和(0。。i-1)=和(0。。j) 反之亦然。实际上,你要计算前缀和和(0。。i) 对于所有i,构建一个哈希表}是我拥有sum(0)的所有位置的列表。。i) =x。然后遍历这个哈希表,一次一个求和,寻找由多个前缀构成的任何和。在所有这些不止一次的加法中,你选择一个由一对相距最远的前缀构成的总和——这是最长的。在
hash_sum
,其中{既然您已经注意到了使该算法线性化所需的关键洞察力,我有点疑惑为什么您在第二个循环中
best_index_hash
中建立了这么多不必要的东西。对于给定的sum x,构成总和的最远前缀对始终是hash_sum[x]
中最小和最大的条目,这必然是第一个条目和最后一个条目(因为这是它们被附加的顺序),因此不需要在它们之间循环。实际上,您甚至根本不需要第二个循环:通过将start_index
视为最右边的端点,可以在第一个循环期间保持最大运行。在要处理任意的差异k:我们需要找到前缀求和到
current_sum
的最左边,而需要找到前缀求和到current_sum - k
的最左边。但那只是first_with_sum{current_sum - k}
。在以下代码未经测试,但应该可以工作:
在开始处设置
first_with_sum{0} = -1
意味着我们不必将从索引0开始的范围视为特殊情况。请注意,该算法并没有改进原始算法的渐近时间或空间复杂性,但它更易于实现,并且在任何包含零和子数组的输入上都将使用较少的空间。在相关问题 更多 >
编程相关推荐