和等于0的最大子阵

2024-03-29 12:44:14 发布

您现在位置:Python中文网/ 问答频道 /正文

这是一个典型的面试问题。给定一个包含正负元素且不含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。我该怎么做呢。任何进一步优化这一点的指针也很有帮助。在


Tags: inforindexifhashabscurrentkeys
3条回答

我同意sundar nataraj的观点,他说这必须发布到代码评审论坛。在

尽管我看了你的代码。虽然我能够理解您的方法,但我无法理解使用Counter的必要性。在

  1. best_index_hash[start_index] = [(0,start_index)]-这里best_index_hash属于Counter类型。你为什么要给它分配一个列表?

  2. for key_1, value_1 in best_index_hash.most_common(1)-您试图得到largest子序列,为此,您使用most_common作为答案。这不是直观的语义。

我很想发布一个解决方案,但我会等你编辑代码片段并加以改进。在


附录

为了好玩,我尝试了这个拼图,我在下面展示了我的努力。我不保证正确性/完整性。在

from collections import defaultdict

def max_sub_array_sum(a, s):
    if a:
        span = defaultdict(lambda : (0,0))
        current_total = 0
        for i in xrange(len(a)):
            current_total = a[i]
            for j in xrange (i + 1, len(a)):
                current_total +=  a[j]
                x,y = span[current_total]
                if j - i > y - x:
                    span[current_total] = i,j

        if s in span:
            i, j = span[s]
            print "sum=%d,span_length=%d,indices=(%d,%d),sequence=%s" %\
                    (s, j-i + 1, i, j, str(a[i:j + 1]))
            return
    print "Could not find a subsequence of sum %d in sequence %s" % \
            (s, str(a))

max_sub_array_sum(range(-6, -1), 0)
max_sub_array_sum(None, 0)
max_sub_array_sum([], 0)
max_sub_array_sum(range(6), 15)
max_sub_array_sum(range(6), 14)
max_sub_array_sum(range(6), 13)
max_sub_array_sum(range(6), 0)

这是我自己的答案,只是为了好玩。在

子序列的数量是二次的,并且子序列求和的时间是线性的,所以最朴素的解应该是立方的。在

这种方法只是对子序列进行彻底的搜索,但是有点小技巧避免了线性求和因子,所以它只是二次型的。在

from collections import namedtuple
from itertools import chain


class Element(namedtuple('Element', ('index', 'value'))):
    """
    An element in the input sequence. ``index`` is the position
    of the element, and ``value`` is the element itself.
    """
    pass


class Node(namedtuple('Node', ('a', 'b', 'sum'))):
    """
    A node in the search graph, which looks like this:

         0      1       2      3
          \    /  \    /  \   /
           0-1     1-2     2-3
              \   /   \   /
               0-2     1-3
                  \   /
                   0-3

    ``a`` is the start Element, ``b`` is the end Element, and
    ``sum`` is the sum of elements ``a`` through ``b``.
    """

    @classmethod
    def from_element(cls, e):
        """Construct a Node from a single Element."""
        return Node(a=e, b=e, sum=e.value)

    def __add__(self, other):
        """The combining operation depicted by the graph above."""
        assert self.a.index == other.a.index - 1
        assert self.b.index == other.b.index - 1
        return Node(a=self.a, b=other.b, sum=(self.sum + other.b.value))

    def __len__(self):
        """The number of elements represented by this node."""
        return self.b.index - self.a.index + 1


def get_longest_k_sum_subsequence(ints, k):
    """The longest subsequence of ``ints`` that sums to ``k``."""
    n = get_longest_node(n for n in generate_nodes(ints) if n.sum == k)
    if n:
        return ints[n.a.index:(n.b.index + 1)]
    if k == 0:
        return []


def get_longest_zero_sum_subsequence(ints):
    """The longest subsequence of ``ints`` that sums to zero."""
    return get_longest_k_sum_subsequence(ints, k=0)


def generate_nodes(ints):
    """Generates all Nodes in the graph."""
    nodes = [Node.from_element(Element(i, v)) for i, v in enumerate(ints)]
    while len(nodes) > 0:
        for n in nodes:
            yield n
        nodes = [x + y for x, y in zip(nodes, nodes[1:])]


def get_longest_node(nodes):
    """The longest Node in ``nodes``, or None if there are no Nodes."""
    return max(chain([()], nodes), key=len) or None


if __name__ == '__main__':

    def f(*ints):
        return get_longest_zero_sum_subsequence(list(ints))

    assert f() == []
    assert f(1) == []
    assert f(0) == [0]
    assert f(0, 0) == [0, 0]
    assert f(-1, 1) == [-1, 1]
    assert f(-1, 2, 1) == []
    assert f(1, -1, 1, -1) == [1, -1, 1, -1]
    assert f(1, -1, 8) == [1, -1]
    assert f(0, 1, -1, 8) == [0, 1, -1]
    assert f(5, 6, -2, 1, 1, 7, -2, 2, 8) == [-2, 1, 1]
    assert f(5, 6, -2, 2, 7, -2, 1, 1, 8) == [-2, 1, 1]

你给出了一个很好的线性时间解(比现在的两个答案更好,都是二次时间),基于这样一个思想:无论何时求和(i。。j) =0,必须是该和(0。。i-1)=和(0。。j) 反之亦然。实际上,你要计算前缀和和(0。。i) 对于所有i,构建一个哈希表hash_sum,其中{}是我拥有sum(0)的所有位置的列表。。i) =x。然后遍历这个哈希表,一次一个求和,寻找由多个前缀构成的任何和。在所有这些不止一次的加法中,你选择一个由一对相距最远的前缀构成的总和——这是最长的。在

既然您已经注意到了使该算法线性化所需的关键洞察力,我有点疑惑为什么您在第二个循环中best_index_hash中建立了这么多不必要的东西。对于给定的sum 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开始的范围视为特殊情况。请注意,该算法并没有改进原始算法的渐近时间或空间复杂性,但它更易于实现,并且在任何包含零和子数组的输入上都将使用较少的空间。在

相关问题 更多 >