arrays - 具有适当总和的数组元素序列的计数

Question

让我们假设我们有一个未排序的整数数组和 2 个给定的整数 L 和 M。我们的任务是找出具有以下属性的序列 a[i]...a[j] 的数量:L<= a[i] + ... + a[j] <= M。

哪种算法最适合解决这个问题？

注意:1<=i<=j<=n，数组的第一个元素是a[1]，不是a[0]。

Answer 1

假设整数都是非负的，你可以使用这个算法(伪代码):

countInRange(a, l, m):
    sumL = 0
    count = 0
    idxM = 0
    i = 1
    idxLast = len(a)
    for idxL = 1 to idxLast:
        sumL = sumL + a[idxL]
        while i <= idxLast and sumL >= l:
            if idxM <= idxL:
                idxM = idxL
                sumM = sumL
            while idxM <= idxLast and sumM <= m:
                idxM = idxM + 1
                if idxM > idxLast:
                    break
                sumM = sumM + a[idxM]
            count = count + idxM - idxL
            sumL = sumL - a[i]
            sumM = sumM - a[i]
            i = i + 1
    return count

此算法以 O(n) 时间复杂度运行:

总的来说，最内层的循环永远不会迭代超过 n 次。这是因为进入循环时idxM的值:

• 永远不会低于 1
• 永远不会高于n
• 总是比上一次进入循环至少大一。

总的来说，中间循环也永远不会执行超过 n 次，因为它会将 i 递增到 n，同样明显外循环为真。

参见 this implementation in Python on repl.it它还提供了一个 O(n²) 算法来检索实际序列本身。请注意，该代码必须进行调整以与 Python 中的零索引数组对齐。