总和小于或等于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,我们记录长度.

嗯......我撒了谎,弗朗西斯科·库佐在评论中抓住了我.上面的代码是不是真的为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:]吗？根据Python wiki中的TimeComplexities文章,从列表中获取切片需要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

根据你在第一次传球中遇到的值,你可以做的更快的检查可以更快地突破第二次传球.

Answer 2

原始答案

最初的问题是找到总和为k的最长子阵列的长度.

您可以浏览列表索引,将每个索引作为您总和的窗口的起点.然后,您将从起始索引到结尾的索引运行,以标记窗口的结束.在每个步骤中,您可以获得总和,甚至更好,将其添加到总和项中.如果总和超过目标,则会突破内循环,继续前进.

它看起来像这样:

def get_longes(a_list, k):
    longest = 0
    length = len(a_list)
    for i in xrange(length):
        s = 0
        for j in xrange(i,length):
            s+=a_list[j]
            if s < k:
                pass
            elif s==k:
                longest = j+1-i
            else:
                break
    return longest

这可以进一步加快,因为在外循环中移动一步时不需要重置窗口大小.实际上,您只需要跟踪窗口大小,如果外部循环继续,则将其减小1.通过这种方式,您甚至可以摆脱内部循环并在O(n)中写入内容:

def get_longest(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<k:  # while the sum is smaller, we increase the window size
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        if s == k:  # if the sum is right, keep its length if it is bigger than the last match.
            longest = max(l_length, longest)
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest

回答更新的问题

更新的问题要求总和等于或小于k的最长子阵列.

对于这个问题,基本方法是相同的,实际上解决方案变得更加简单,因为现在我们在总和上只有两个条件,即:

1)总和小于或等于k.

2)总和大于k.

解决方案如下:

def get_longest_smaller_or_equal(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<=k:  # while the sum is smaller, we increase the window size
            longest = max(l_length, longest)
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest