【算法题】返回子序列中总和大于给定的值

问题

给定一个序列，其中有多个子序列，每个子序列中存了一些值。另外还给了一个数量，只要在每个子序列中依次遍历直到前面所有的元素加起来不小于这个给定的数量，就把这些元素放在一个新的列表中，最后将所有符合条件的子序列的结果一起返回。

例如：给的序列为[[10, 30, 5, 6, 8], [20, 42, 11], [3]]，数量为50，那么函数执行结果就是[[10, 30, 5, 6], [20, 42]]；给的序列为[[20, 20], [5, 5, 30]]，数量也为50，那么函数执行结果就是False，因为两个子序列中没有任何一个的总和加起来不小于 50。

解析

遍历子序列中的元素，然后计算子序列第一个元素一直到当前位置的总和是否不小于给定数量，如果是的话就将子序列中一直到当前位置的值保存，同时跳出遍历当前子序列循环的操作，进入下一个子序列中，具体实现代码如下：

def match_num(li, num):
    tem_li = []
    for sub_li in li:
        for i in range(len(sub_li)):
            if sum(sub_li[:i]) >= num:
                tem_li.append(sub_li[:i])
                break
    return tem_li if tem_li else False

输出一下结果：

>>> match_num([[10, 30, 5, 6, 8], [20, 42, 11], [3]], 50)
[[10, 30, 5, 6], [20, 42]]
>>> match_num([[20, 20], [5, 5, 30]], 50)
False

思考

还是类似上面的问题，不过把条件改成即使任何一个子序列的总和都小于给的数量，但只要依次遍历的多个子序列中的值加起来不小于给的数量，就返回这些结果。另外，如果在某个子序列中就找到了总和不小于给的数量的情况，就不需要再考虑多个子序列的值累加。

例如：给的序列为[[20, 20], [5, 5, 30]]，数量也为50，那么函数执行结果就是[[20, 20], [5, 5]]，因为虽然两个子序列中没有任何一个的总和加起来不小于 50，但是第一个子序列中的所有值加上第二个子序列的前两个值符合条件，因此返回这些结果。

计算方法前面类似上面给出的算法，先在每个子序列中进行遍历。子序列中都没有找到我们想要的结果后，再开始对子序列进行累加计算。不过我们需要增加两个变量，其中一个保存到目前为止已经求得的累加结果，另一个标识是否在某个子序列中找到了总和不小于给定数量的情况。

def match_num(li, num):
    tem_li = []
    for sub_li in li:
        for i in range(len(sub_li) + 1):
            if sum(sub_li[:i]) >= num:
                tem_li.append(sub_li[:i])
                break
    if tem_li:
        return tem_li
    else:
        sumary = 0
        flag = False
        for sub_li in li:
            for i in range(len(sub_li) + 1):
                if sum(sub_li[:i]) >= num - sumary:
                    tem_li.append(sub_li[:i])
                    flag = True
                    break
            if not flag:
                tem_li.append(sub_li[:i])
                sumary += sum(sub_li[:i])
            else:
                break
        return tem_li if flag else False

>>> match_num([[10, 30, 5, 6, 8], [20, 42, 11], [3]], 50)
[[10, 30, 5, 6], [20, 42]]
>>> match_num([[20, 20], [5, 5, 40], [10, 2]], 50)
[[5, 5, 40]]
>>> match_num([[20, 20], [5, 5, 30], [10, 2]], 50)
[[20, 20], [5, 5]]
>>> match_num([[20, 20], [1, 1, 2]], 50)
False