最长子字符串的长度合为S

Question

我在一次面试中被问到以下问题，但我无法给出最优的答案。

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

输入：1.可变大小的数组，仅包含{-1,0,1}元素。

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

2.一个整数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：我提出的问题没有版权问题。

- kishoredbn

---

子数组是否是连续的？ - Tamas Ionut

@TamasIonut 它是一个连续的子数组。 - kishoredbn

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)

- Juan Lopes

---

这段代码输出 (4,15)，意思是答案长度为 15？ - shole

@shole 不，它意味着从索引4开始到索引15结束的字符串是最长的。答案实际上是15-4+1 = 12。 - Juan Lopes

@JuanLopes 似乎您的解决方案不能适用于所有情况。这是一个 solve([-1, 0, 1, 1, 1, 1, 1, 0, 0, 1], 4) 的解决方案。 - kishoredbn

@ikis没错，但我认为0是一个特殊情况，因为它是唯一可以从空数组中实现的。因此，只需在开始时将0:0放入表格中即可。(已经编辑完毕) - Juan Lopes

Answer 2

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

• 取出所有的0。
• 确保有足够的1（对于正数）或-1（对于负数）。
• 如果没有，则出现错误。
• 然后选择正确数量的1/-1，以使用完所有“其他值”。

最后一点故意有些模糊（您可以通过解决一些例子来考虑它）。

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

- Gordon Linoff

Answer 3

算法概述：

1. 定义Lo[x]为“和为x的最长前缀和的长度”
2. 定义Sh[x]为“和为x的最短前缀和的长度”
3. 对于所有x，Ans = max(Lo[x+S] - Sh[x])，其中S为给定值，可以通过遍历数组一次找到

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

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

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

- shole