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

Question

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

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

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

示例：A[] = {1, 0, 0, 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

如果只有-1、0和1这三个值，那么你可以通过计算-1、0和1的值的个数来解决这个问题。然后应用一个公式。效果为：

取全0。
确保你有足够的 1（正数，-1 负数）。
如果不是，报错。
然后选择正确数量的 1s/-1s 以便用完所有 "other values"

最后一点故意说的有点含糊（大家可以举个例子想想）。

重点是有了三个值，就可以填充三个值。然后你可以使用一些规则来获得最长的适当和。

Answer 2

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

但是，在每次插入之前，检查散列 table 是否已经包含 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)

Answer 3

算法概要：

定义Lo[x]为总和为x的最长前缀和的长度
定义Sh[x]为与x相加的最短前缀和的长度
Ans = max(Lo[x+S] - Sh[x]) for all x, 循环数组一次就可以找到

Lo[] & Sh[] 的内存大小都是 O(n) 因为所有元素都在 {-1,0,1}

为了处理负和，其中一种方法是将范围 -n..n 映射到 0..2n 以便索引 x 可以表示（因此两个数组的大小都是 O(2n) = O(n))

计算前缀和，只需要遍历数组一次，更新数组即可，Lo[] & Sh[]都可以在O(n)

中计算

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

Length of largest substring adds up to S

arrays

algorithm

sub-array