logo标签列表

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

pythonalgorithmdynamic-programming
22

在一次面试中，我被问到这个问题：给定一些正整数数组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

第一个例子是如何工作的？在[1, 2, 3]中没有连续的子数组，使得整数加起来等于4。 - bigblind
我们只需要找到最长的长度，而不需要具体的子数组。 - nonsequiter
4
好的，但是第一个案例仍然没有意义。在那里有两个长度为2的子数组：[1, 2]和[2, 3]。只有当你认为数组是循环的时候，这个例子才有意义。也就是说，数组的最后一个元素与第一个元素相邻。此时，[3,1]也是一个连续的子数组，加起来为4。 - bigblind
3
你的意思是“最长连续子数组和为k的长度”吗？ - samgak
9个回答
29
您可以在线性时间（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:]吗？根据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

第二次遍历时，您可以基于第一次遍历中遇到的值进行检查，以更早地跳出循环。

那非常优雅！ - hvwaldow
@FranciscoCouzo 确实。我会添加O(n)版本以完整性。 - bigblind
1
哦，所以它们需要加起来小于等于k，而不是恰好等于k，这很有道理。 - bigblind
1
我的问题说明了数组是非循环的，且总和小于等于k，所以我在没有使用s = s + s和条件if subarray_sum == k的情况下进行了测试，结果非常好。 - nonsequiter
你好。对于 [3, 1, 2, 1] 和 k = 5，它是如何工作的？上面的答案返回 -1，但实际上应该是 3。 - piepi
显示剩余4条评论
8

原始答案

最初的问题是找到总和为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
1
我喜欢这个答案的教学方法：首先是基本思路及其实现，然后通过利用子数组的连续性来加速代码的改进，同样附带有实现。此外，这个答案不一定需要遍历整个列表，这与@bigblind的答案不同。这个解决方案在索引加上窗口长度达到列表长度时就停止了……非常好！ - dendragon
@dendragon 谢谢！你说得对，这个解决方案不一定需要遍历整个列表，但是在每次迭代中，它需要检查窗口是否在列表内（if i+l_length==length 语句），这是一个条件，如果你把窗口放在索引的左边，就没有这个条件，就像 @bigblind 所做的那样。所以我认为他的答案可能更快。 - j-i-l
哦，好的。我没有意识到这一点。嗯，我猜如果k相对于列表中的单个元素很大，那么你的答案可能仍然更快。 - dendragon
当我运行这个程序时，它未通过上述第一个输入。 - nonsequiter
@nonsequiter 它将第一个输入视为不可解决的（因此返回长度为0）。这是您所提出的原始问题的正确解决方案（等于k）。我将使其适应您对问题所做的修改（即小于或等于k）。 - j-i-l
3

我认为这个方法可行...（递归地并从问题中去掉“连续”的要求，因为这似乎与问题提供的示例输出不匹配），而且OP提到了问题是：

给定一些正整数数组s，找到最长的子数组的长度，使得所有值的总和等于某个正整数k。

def longest_sum(input_list, index, num_used, target_number):
    if target_number == 0:
        return num_used
    if index >= len(input_list):
        return 0

    # Taken
    used_1 = longest_sum(input_list, index + 1, num_used + 1, target_number - input_list[index])
    # Not taken
    used_2 = longest_sum(input_list, index + 1, num_used, target_number)
    return max(used_1, used_2)


if __name__ == "__main__":
    print(longest_sum([2, 1, 8, 3, 4], 0, 0, 6))
    print(longest_sum([1, 2, 3], 0, 0, 4))
    print(longest_sum([3, 1, 2, 1], 0, 0, 4))
    print(longest_sum([1, 2, 7, 8, 11, 12, 14, 15], 0, 0, 10))
    print(longest_sum([1, 2, 3], 0, 0, 999))
    print(longest_sum([1, 1, 1, 1, 1, 1, 4], 0, 0, 6))

输出：

3
# BorrajaX's note: 2 + 1 + 3
2
# BorrajaX's note: 3 + 1
3
# BorrajaX's note: 1 + 2 + 1
3
# BorrajaX's note: 1 + 2 + 7
0
# BorrajaX's note: No possible sum
6
# BorrajaX's note: 1 + 1 + 1 + 1 + 1 + 1

编辑 01：

如果您想获取使总和最长的列表，可以按照以下方式执行：

import copy


def longest_sum(input_list, used_list, target_number):
    if target_number == 0:
        return used_list

    if not input_list:
        return []

    # Taken
    used_list_taken = copy.copy(used_list)
    used_list_taken.append(input_list[0])
    used_1 = longest_sum(input_list[1:], used_list_taken, target_number - input_list[0])

    # Not taken
    used_list_not_taken = copy.copy(used_list)
    used_2 = longest_sum(input_list[1:], used_list_not_taken, target_number)
    if len(used_1) > len(used_2):
        return used_1
    else:
        return used_2


if __name__ == "__main__":
    print(longest_sum([2, 1, 8, 3, 4], [], 6))
    print(longest_sum([1, 2, 3], [], 4))
    print(longest_sum([3, 1, 2, 1], [], 4))
    print(longest_sum([1, 2, 7, 8, 11, 12, 14, 15], [], 10))
    print(longest_sum([1, 2, 3], [], 999))
    print(longest_sum([1, 1, 1, 1, 1, 1, 4], [], 6))

你将看到：

[2, 1, 3]
[1, 3]
[1, 2, 1]
[1, 2, 7]
[]
[1, 1, 1, 1, 1, 1]

提示 1: 我真的不知道如何在没有递归提供的快速回溯能力的情况下完成这个任务... 抱歉 :-(

提示 2: 如果这不是你想要的（我从要求中去掉了“连续”的要求），请告诉我，我会删除这个答案。

2

如果s是非环状的，可以使用一些简单的方法来缩短长度：滑动窗口，逐渐减小窗口大小。

def maxlen(s, k):
    for win in range(k, 0, -1):
        for i in range(0, len(s) - win):
            if sum(s[i:i+win]) == k:
                return win
    return None

s = [3,1,2,3]
k = 4
print(maxlen(s, k))
2
这里有一个适用于任何可迭代对象 s（甚至是迭代器）的解决方案。它本质上与 bigblind's answer 的算法相同，但如果 k 相对于 s 中的值很大（使相关子序列的长度较长），则效率更高：
import itertools

def max_length(s, k):
    head, tail = itertools.tee(s)
    current_length = current_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.

    for i in head:
        current_length += 1
        current_sum += i

        while current_sum > k:
           current_length -= 1
           current_sum -= next(tail)

        if current_sum == k:
            max_len = max(max_len, current_sum)

    return max_len

因为我们在迭代时不保留正在检查的子序列列表，所以这种基于迭代器的方法只有在您只需要最长子序列的长度而不是其实际内容时才有用。
如果您想获得最长子序列的副本，可以使用bigblind答案的另一种变体，使用collections.dequeue而不是列表（因此从左侧弹出很快），并像我的代码一样跟踪运行总和（因此您无需反复调用sum）：
import collections

def max_subsequence(s, k):
    current = collections.dequeue()
    current_sum = 0
    max_len = -1
    max_seq = None # returns None if there is no valid subsequence.

    for i in s:
        current.append(i)
        current_sum += i

        while current_sum > k: # Shrink from the left efficiently!
           current_sum -= current.popleft()

        if current_sum == k:
            if len(current) > max_len:
                max_len = len_current
                max_seq = list(current) # save a copy of the subsequence

    return max_seq

如果您的问题标题具有误导性，而且您实际上并不关心子序列是否是连续的，那么我认为您当前的动态规划方法可以做到您想要的。我只是不太确定我理解您的循环意图。我认为最自然的方式是在输入项上进行外部循环，并在包括该值的潜在总和（这些总和是lengths列表中的索引）上进行第二个循环。我还建议将None用作除0以外的所有长度的初始值，因为否则很难在没有特殊情况的情况下使条件正确工作。
def max_length(s, k):
    lengths = [None for _ in range(k+1)]
    lengths[0] = 0

    for x in s:
        for i in range(k, x-1, -1): # count down to avoid duplication
            if lengths[i-x] is not None and (lengths[i] is None or
                                             lengths[i-x] >= lengths[i]):
                lengths[i] = lengths[i-x] + 1

    return lengths[k]
1

解决这个问题的方法

O(n) - 双指针法

将第一个元素初始化为s和e，subArray_sum = arr[0]

现在如果subArray_sum < k，则将e递增，同时保证subArray_sum <= k

一旦subArray_sum变成>= k，则将s递增，直到它变成<= k

O(nlog n) - 二分查找

考虑所有可能的子数组长度i.(1 <= i <= n)。在所有长度为i的子数组中，找到具有最小和的子数组。对于给定值i，这可以在O(n)内完成。现在对于任何长度为i的子数组，如果长度为i但最小和的子数组的和<= k，则可以找到和<= k的i长度的子数组。现在要找到最长的i，使得存在长度为i的子数组且子数组和<= k。 在范围为start = 1和end = n的i上进行二分搜索;

O(n*n) - 暴力法

考虑所有可能的子数组(n*n个)，并找到最长的和<= k的子数组

以上问题的变体

长度最长的子数组，其平均值小于或等于k

以上所有方法在此同样适用

0

我刚刚偶然发现了这个有趣的讨论。

在阅读和思考不同的方法时，我想知道为什么没有人提出当无法找到更长的子数组时立即返回。

max_len > array_len - subarray_start

这会增加一个额外的整数值存储，但对于循环来说只需要增加一次减法和一次比较的开销。

这两个操作都不应该太重，对于更长的数组和子数组可能会有益。

将其集成到bigblind的解决方案中：

def max_length(s, k):
    # These two mark the start and end of the subarray that `current` used to be.
    array_len = len(s)
    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 early when it is clear no longer subarray can be found
        if max_len > array_len - subarray_end: return max_len

    return max_len

我用原始输入以及几个更长的列表和更高的k值（例如max_length([1,3,1,0,1,4,2,1,4,1], 4)）进行了测试，并在旁边记录日志输出，以便能够计算循环次数。

真正让我惊讶的是：我的改动可能只节省了一两个循环。如果我们真的调整测试输入，可能会有更多节省的情况，但总体来说，它并没有做比添加更多代码行更多的事情。

我只是留下这篇文章，以防其他人也有类似的想法。

0

CODE IN CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve(vector<int>& arr, int k) {
    int n = arr.size();
    int subarray_start = 0;
    int subarray_end = 0;

    int subarray_sum = 0;
    int max_len = -1; 
    for(int i=0;i<n;i++){
        subarray_sum += arr[i];
        subarray_end += 1;
        while(subarray_sum>=k){
            subarray_sum -= arr[subarray_start];
            subarray_start ++;
        }
        max_len = max(max_len,subarray_end - subarray_start);
    }
    cout<<max_len;
        
}

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin >> v[i];
    solve(v,k);
    return 0;
}

[执行的代码截图][输出结果截图]

0

这篇文章可以帮助你很多。

https://e2718281828459045.wordpress.com/2013/08/19/longest-subarray-whose-sum-k/

可以使用求和数组+二分查找来解决。
首先的观察是，如果我们考虑第i个元素，那么我们必须继续考虑(i+1)th及其之后的元素。也就是说，我们需要按顺序添加所有元素，直到最后一个元素或者达到所需和。因此，顺序很重要。
如何添加这些数字呢？有n种方法。第一种方法是从第一个元素开始加，一直加到k或者最后一个元素为止。第二种方法是从第二个元素开始加，一直加到k或者最后一个元素为止。
因此，朴素算法会给出O(n²)的解决方案。我们如何改进它？显然，这不是期望的解决方案。对于每个i，
我们正在计算元素的总和，并检查总和是否超过了给定值'k'。为了避免这种情况，我们可以创建一个求和数组。

记住，每当你遇到一个序列求和问题（或给定数组中连续元素的总和），很可能可以使用求和数组技术来解决。求和数组是使用给定数组构造的新数组。它可以使用以下公式生成：

sum[i] = sum[i−1] + array[i]

对于所有的 i>0。

sum[i]=array[i]

for i=0.

可以在O(n)的时间内创建一个数组求和。找到第i个和第j个之间的和变得很容易。这是它们之间的差异，

sum[j]−sum[i], j>i

会给出答案，但仍然是O(n2)的解决方案。
问题在于对于每个i的值，我们需要花费O(n)的时间来找到j。
那么我们如何减少这个时间？
Bingo！这里引入了二分搜索。通过在区间i和n上使用修改后的二分搜索，我们可以在O(logn)的时间内找到j。因此，它只需要O(nlogn)的时间。我们需要一个额外的变量和条件来存储子数组的长度，即j−i。

希望这有所帮助。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接