确定一个数字大于另一个数字的索引

Question

我有这个功能，应该告诉索引数字列表的总和在哪里等于或大于一系列数字。我已经完成了此检查索引的实现，但是对于列表中的项目数大于1,000,000来说太慢了。我如何才能提高速度？听说可以使用bisect.bisect_left，但不确定。

n基本上是v中元素的数量，这是要求和的元素列表，我正在尝试查找其索引。 noq是vom中元素的数量，这就是我要总结的内容。

[8 3 10 22 1]和20的示例...列表大于或等于20的索引为3

import math
import os
import random
import re
import sys

import math 

def bossBusiness (n, v, noq, vom):

    adder = 0
    indicies = []
    count = 1

    for i in vom:

        for t in v:
            if (sum(v) < i):
                indicies.append(-1)
                break

            adder = adder + t 
            if (adder >= i):
                indicies.append(count)
                count = 1
                adder = 0
                break
            else:
                count = count + 1

    for i in indicies:

        fptr.write(str(i) + '\n')

Answer 1

计算前缀和，因此您的[8, 3, 10, 22, 1]变为[8, 11, 21, 43, 44]，然后使用二进制搜索（例如，您提到的使用bisect）。

Answer 2

def bossBusiness (n, v, noq, vom):

    adder = 0
    indicies = []
    count = 1

    res = [sum(v[ : i + 1]) for i in range(len(v))]

    for i in vom:


        if (sum(v) < i):
            indicies.append(-1)

        else:

            indicies.append((1 + (bisect.bisect_left(res, i))))



    for i in indicies:

        fptr.write(str(i) + '\n')