arrays - 最大子串的长度加起来为 S

Question

我在面试中被问到以下问题，我无法给出最佳答案。

问题:编写一个程序，可以找到总和为 S 的最大连续子数组的长度。给定一个可变大小的数组和一个整数。

输入:1. 一个可变大小的数组，它只能有 {-1, 0, 1} 个元素。

示例:A[] = {1, 0, 0, 1, -1, 1, 1, 1, 1}

1. 一个整数S，

例子:S = 4

输出:8

解释:A 的最大连续子数组加起来等于 S=4:{1, 0, 0, 1, -1, 1, 1, 1} 或 {0, 0, 1, -1, 1 , 1, 1, 1}

约束:应该在 O(N) 内完成

我已经解决了这个问题，但是无法满足时间复杂度。任何人都可以提供可以在 O(N) 中解决此问题的解决方案。

PS:我提出的问题没有版权问题。

Answer 1

遍历数组，将总和存储到变量中的当前元素。对于每个总和值，将其放入 O(1) 的哈希表中(如果它还不存在)，映射到它出现的索引。

但是，在每次插入之前，检查哈希表是否已经包含 current_sum - S。如果包含，则意味着子数组 [previous_index+1..current_index] 具有总和 S。

即使数组包含 {-1, 0, 1} 以外的元素，这也有效。

这是一个示例 Python 代码:

def solve(A, S):
    table = {0: 0}
    answer = None
    total = 0
    for i, x in enumerate(A):
        total += x
        if total - S in table:
            candidate = (table[total-S], i)
            if answer is None or candidate[1] - candidate[0] > answer[1] - answer[0]:
                answer = candidate
        if total not in table: 
            table[total] = i+1

    return answer

print solve([-1, 0, 1, 1, 1, 1, 1, 0, 0, 1], 4)