回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我怎样才能加快实施下面的问题陈述?我有一个正确的解决方案,通过了每个小输入测试。但是,它超出了较大输入的时间限制。我当前的实现是数组大小的二次型</p>
<p><strong>问题陈述</strong></p>
<p>您有一个非负整数的未排序<code>array</code>arr和一个数<code>s</code>。在<code>arr</code>中查找和等于<code>s</code>的最长连续子数组。返回表示其包含边界的两个整数。如果有多个可能的答案,请返回左边界最小的答案。如果没有答案,请返回[-1]</p>
<p>您的答案应该是基于1的,这意味着数组的第一个位置是1而不是0</p>
<p><strong>实施</strong></p>
<pre><code>def findLongestSubarrayBySum(s, arr):
"""Return a two-element array that represent the bounds of the subarray."""
ans = [-1]
for left in range(len(arr)):
curr_sum = arr[left]
if curr_sum == s and len(ans) == 1:
ans = [left + 1] * 2
for right in range(left + 1, len(arr)):
curr_sum += arr[right]
if curr_sum == s:
# First found soltion
if len(ans) == 1:
ans = [left + 1, right + 1]
# Left bound is right bound
elif ans[1] == ans[0]:
ans = [left + 1, right + 1]
# Longer subarray
elif ans[1] - ans[0] < right - left:
ans = [left + 1, right + 1]
elif curr_sum > s:
break
return ans
if __name__ == '__main__':
# s = 12 # ans = [2, 4]
# arr = [1, 2, 3, 7, 5]
# s = 15 # ans = [1, 5]
# arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# s = 15 # ans = [1, 8]
# arr = [1, 2, 3, 4, 5, 0, 0, 0, 6, 7, 8, 9, 10]
# s = 3 # ans = -1
# arr = [1, 1]
# s = 3 # ans = -1
# arr = [2]
# s = 468 # ans = [42, 46]
# arr = [135, 101, 170, 125, 79, 159, 163, 65, 106, 146, 82, 28,
# 162, 92, 196, 143, 28, 37, 192, 5, 103, 154, 93, 183, 22,
# 117, 119, 96, 48, 127, 0, 172, 0, 139, 0, 0, 70, 113, 68,
# 100, 36, 95, 104, 12, 123, 134]
# s = 3 # ans = [1, 1]
# arr = [3]
# s = 0 # ans = [2, 2]
# arr = [1, 0, 2]
s = 3 # ans = [1, 3]
arr = [0, 3, 0]
print(findLongestSubarrayBySum(s, arr))
</code></pre>