总和等于 s 的最长子数组

Question

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

问题陈述

您有一个未排序的 array arr 非负整数和一个数字 s。在 arr 中找到最长的连续子数组，其总和等于 s。 Return 两个整数，表示其包含边界。如果有多个可能的答案，return 左边界最小的那个。如果没有答案，return [-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

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

[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 2

您可以使用两个指针方法，其时间复杂度为O(n)，space复杂度为O(1)。可以找到类似的问题和两个指针解决方案here。

Answer 3

这里是两指针方法的实现，它在时间上是线性的并且在额外 space 开销方面是常数。它类似于您的解决方案，只是我们不会在每次循环迭代时从大小 0 重新生成 window 。由于只求最早最大的window，右指针只会增加（而不是增加和减少），时间复杂度容易证明。

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

总和等于 s 的最长子数组

Longest subarray that has a sum equal to s

python

arrays

algorithm

performance

time-complexity