python - 和小于等于k的最长子数组长度

Question

在一次采访中有人问我这个问题:给定一些正整数数组 s，找到最长子数组的长度，使其所有值的总和小于或等于某个正整数 k。每个输入总是至少有一个解决方案。数组不是圆形的。

我开始编写一个动态规划解决方案，该解决方案的工作原理是在从 0 到 k 越来越大的值处找到最大长度。

这是我在 python 中的代码，其中有一个我似乎找不到的错误，我的答案总是有几位数字:

def maxLength(s, k):
    lengths = [0 for x in range(k)]
    for i in range(1,k+1):
        for j in range(len(s)):
            if s[j] <= i and lengths[i - s[j]] + 1 > lengths[i]:
                lengths[i] = lengths[i - s[j]] + 1
        if i + 1 == len(s):
            break
    return lengths[-1]

输入 1:s = [1,2,3], k = 4

输出 1:2

输入 2:s=[3,1,2,1], k = 4

输出 2:3

Answer 1

您可以在线性 (O(n)) 时间内完成此操作:

def max_length(s, k):
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1

        # After the previous while loop, subarray_sum is guaranteed to be 
        # smaller than or equal to k.
        max_len = max(max_len, subarray_end - subarray_start)

    return max_len

最初的问题有些困惑，我认为我们正在寻找总和 ** 等于(但不小于)k* 的子数组。我的原始答案如下。那里也有关于此解决方案线性度的信息，如果您有兴趣，请继续阅读。

原始答案

这是我的做法:

def max_length(s, k):
    current = []
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        while sum(current) > k: # Shrink the array from the left, until the sum is <= k.
           current = current[1:]
        if sum(current) == k:
            max_len = max(max_len, len(current))

    return max_len

这利用了我们正在寻找一个连续的子数组来获得具有线性 (O(n)) 时间复杂度的解决方案这一事实。 current 是我们当前尝试创建一个总和为 k 的子数组。我们遍历 s 并将每个元素从 s 添加到 current。如果 current 的总和变得太大(大于 k)，我们从 current 的左边移除元素，直到总和小于或等于 k。如果在任何时候，总和等于k，我们记录长度。

---

嗯……我撒谎了，Francisco Couzo 在评论中捕获了我。上面的代码并不是真正的 O(n) 我正在调用 len(current) 和 sum(current)，它们最多占用 n步骤，使算法以二次时间运行 (O(n^2))。我们可以通过自己跟踪 current 的大小和总和来解决这个问题。

下面的版本让我们更接近 O(n)，但我在编写它时注意到一个问题。

def max_length(s, k):
    current = []
    len_current = 0
    sum_current = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        sum_current += i
        len_current += 1
        while sum_current > k: # Shrink the array from the left, until the sum is <= k.
            sum_current -= current[0]
            current = current[1:]
            len_current -= 1
        if sum_current == k:
            max_len = max(max_len, len_current)

    return max_len

这段代码可能看起来是 O(n)，如果它是用 Go 编写的，它就是。看到 current = current[1:] 了吗？根据TimeComplexities article in the Python wiki ，从列表中取出一个切片需要 O(n)。

我从一开始就找不到删除元素的列表操作，直到我突然意识到我不必这样做。 current 总是 s 的连续子数组，那么为什么不标记它的开始和结束呢？

所以这是我的最终解决方案:

def max_length(s, k):
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1
        if subarray_sum == k:
            max_len = max(max_len, subarray_end - subarray_start)

    return max_len

---

如果您认为数组是循环的(问题中的第一个示例案例似乎表明了这一点)，您可以遍历数组两次:

def max_length(s, k):
    s = s + s
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1
        if subarray_sum == k:
            max_len = max(max_len, subarray_end - subarray_start)

    return max_len

根据您在第一遍中遇到的值，您可能可以进行检查以更快地突破第二遍。