我在面试中被问到以下问题,我无法给出最佳答案。
问题:编写一个程序,可以找到总和为 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:我提出的问题没有版权问题。
最佳答案
遍历数组,将总和存储到变量中的当前元素。对于每个总和值,将其放入 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)
关于arrays - 最大子串的长度加起来为 S,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35734920/