和等于s的最长子数组

Question

如何加快以下问题陈述的执行速度？我有一个正确的解决方案，通过每一个测试的小输入。但是，它超过了较大输入的时间限制。我当前的实现是数组大小的二次型。

你的答案应该是基于1的，这意味着数组的第一个位置是1而不是0。

实施

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))

Answer 1

如果输入包含负数，则在概念上使用前缀和，在实践中使用哈希表。prefixes_j-prefixes_i=s。对于每个prefixes_j，它只是一个单一的累加和，检查hash表中是否存在键prefixes_j-s；之后，如果表中不存在和，则将其作为指向当前索引的键插入。存储在该键的值将是看到前缀和的第一个索引，这样，最左边的索引将返回重复的索引。

[1, 2, 3, 7, 5]  s = 12

sum 1
hash 1

sum 3
hash 1, 3

sum 6
hash 1, 3, 6

sum 13
hash contains 1
found 13 - 12 = 1
record length 3

etc...

如果输入不包含负数，可以使用这样的思想，即右指针可以在和超过s时立即停止，然后递增左指针，直到它再次变小，以这种方式交替指针递增，这样每个指针总共遍历列表一次。