我遇到了以下问题:
给定一个整数数组arr,一个正整数k和一个整数s,你的任务是找到长度不大于k且和等于s的非空连续子数组的数量。
对于arr = [1,2,4,-1,6,1],k = 3和s = 6,输出应为solution(arr,k,s) = 3。
- 在长度为1的连续子数组中,有1个子数组与和等于s = 6,它是[6], - 在长度为2的连续子数组中,有1个子数组与和等于s = 6,它是[2,4], - 在长度为3的连续子数组中,有1个子数组与和等于s = 6,它是[-1,6,1]。
请注意,子数组[1,2,4,1]的和也为s,但它的长度大于k,因此不适用。
所以答案是3。
以下是我在Python中的尝试。我的想法是将每个前缀和的出现索引存储在字典中。例如,如果前缀和6在索引1和3处出现,则字典中的条目将是6:[1,3]。然后,在每一步中,我们可以检查是否已经遇到了目标和s(if curr - s in d:)以及子数组的范围。
这通过了10/15个测试用例,但超过了余下的隐藏用例的时间限制。如果有人有优化算法,我将不胜感激。
给定一个整数数组arr,一个正整数k和一个整数s,你的任务是找到长度不大于k且和等于s的非空连续子数组的数量。
对于arr = [1,2,4,-1,6,1],k = 3和s = 6,输出应为solution(arr,k,s) = 3。
- 在长度为1的连续子数组中,有1个子数组与和等于s = 6,它是[6], - 在长度为2的连续子数组中,有1个子数组与和等于s = 6,它是[2,4], - 在长度为3的连续子数组中,有1个子数组与和等于s = 6,它是[-1,6,1]。
请注意,子数组[1,2,4,1]的和也为s,但它的长度大于k,因此不适用。
所以答案是3。
以下是我在Python中的尝试。我的想法是将每个前缀和的出现索引存储在字典中。例如,如果前缀和6在索引1和3处出现,则字典中的条目将是6:[1,3]。然后,在每一步中,我们可以检查是否已经遇到了目标和s(if curr - s in d:)以及子数组的范围。
这通过了10/15个测试用例,但超过了余下的隐藏用例的时间限制。如果有人有优化算法,我将不胜感激。
import collections
def solution(arr, k, s):
res = 0
curr = 0
d = collections.defaultdict(list)
d[0].append(-1)
for i, num in enumerate(arr):
curr += num
if curr - s in d:
for idx in d[curr-s]:
if i - idx <= k:
res += 1
d[curr].append(i)
return res
for idx in d[curr-s]:
,你可以通过在字典中存储的索引上进行二分查找来消除它。 - Photon