总和等于s的最长子数组

Question

我怎样才能加快实施下面的问题陈述？我有一个正确的解决方案，通过了每个小输入测试。但是，它超出了较大输入的时间限制。我当前的实现是数组大小的二次型

问题陈述

您有一个非负整数的未排序arrayarr和一个数s。在arr中查找和等于s的最长连续子数组。返回表示其包含边界的两个整数。如果有多个可能的答案，请返回左边界最小的答案。如果没有答案，请返回[-1]

您的答案应该是基于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

您可以使用时间复杂度为O(n)、空间复杂度为O(1)的双指针方法。类似的问题和双指针解决方案可以在here中找到

Answer 2

如果输入包含负数，则在概念上使用前缀和，在实践中使用哈希表prefixes_j - prefixes_i = s。对于每个prefixes_j（简单地说是一个累加和），检查哈希表中是否存在键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时立即停止的想法，然后递增左指针直到其再次变小，交替指针以这种方式递增，因此每个指针总共遍历列表一次

Answer 3

这里是双指针方法的一个实现，它在时间上是线性的，在额外的空间开销上是恒定的。它与您的解决方案类似，只是我们不会在每次循环迭代中从0大小重新生成窗口。因为您只需要最早、最大的窗口，所以右指针只会不断增加（而不是增加和减少），这使得时间复杂性很容易证明

def findLongestSubarrayBySum(s, arr):
    """Return a two-element array that represent the bounds of the subarray."""
    ans = [-1, -2]
    s -= arr[0]
    right = 0
    for left in range(len(arr)):
        while right < len(arr) - 1 and s >= arr[right + 1]:
            s -= arr[right + 1]
            right += 1
        if s == 0 and right - left > ans[-1] - ans[0]:
            ans = [left + 1, right + 1]
        s += arr[left]
    if ans[0] == -1:
        return [-1]
    return ans