3

我在一次采访中被问到以下问题，我无法给出最佳答案。

问题：编写一个程序，找出总和为 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：我提出的问题没有版权问题。

4

3 回答 3

3

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

但是，在每次插入之前，检查哈希表是否已经包含 current_sum - S。如果包含，则表示子数组 [previous_index+1..current_index] 有 sum 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)
于 2016-03-02T00:49:05.090 回答
1

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

  • 取所有的 0。
  • 确保您有足够的 1（对于正数，-1 对于负数）。
  • 如果不是，则报错。
  • 然后选择正确数量的 1s/-1s，这样你就用完了所有的“其他值”

最后一点故意有点模糊（你可以通过一些例子来思考）。

关键是，使用三个值，您可以填充这三个值。然后您可以使用一些规则来获得最长的适当总和。

于 2016-03-01T22:37:37.320 回答
1

算法概要：

  1. 将 Lo[x] 定义为总和为 x 的最长前缀和的长度
  2. 将 Sh[x] 定义为总和为 x 的最短前缀和的长度
  3. 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)

于 2016-03-02T07:34:53.290 回答