Google访谈:查找给定整数数组中的所有连续子序列,其总和落在给定范围内.我们能做得比O(n ^ 2)好吗？

Question

给定一个整数数组和一个范围(低,高),找到数组中所有连续的子序列,它们在该范围内具有和.

有没有比O(n ^ 2)好的解决方案？

我尝试了很多,但找不到比O(n ^ 2)更好的解决方案.请帮我找到更好的解决方案或确认这是我们能做的最好的.

这就是我现在所拥有的,我假设范围被定义为[lo, hi].

public static int numOfCombinations(final int[] data, final int lo, final int hi, int beg, int end) {
    int count = 0, sum = data[beg];

    while (beg < data.length && end < data.length) {
       if (sum > hi) {
          break;
       } else {
          if (lo <= sum && sum <= hi) {
            System.out.println("Range found: [" + beg + ", " + end + "]");
            ++count;
          }
          ++end;
          if (end < data.length) {
             sum += data[end];
          }
       }
    }
    return count;
}

public static int numOfCombinations(final int[] data, final int lo, final int hi) {
    int count = 0;

    for (int i = 0; i < data.length; ++i) {
        count += numOfCombinations(data, lo, hi, i, i);
    }

    return count;
}

Answer 1

O(n)时间解决方案:

您可以扩展问题的"确切"版本的"双指针"概念.我们将维护变量a,b使得表单上的所有区间xs[i,a), xs[i,a+1), ..., xs[i,b-1)在所寻求的范围内具有总和[lo, hi].

a, b = 0, 0
for i in range(n):
    while a != (n+1) and sum(xs[i:a]) < lo:
        a += 1
    while b != (n+1) and sum(xs[i:b]) <= hi:
        b += 1
    for j in range(a, b):
        print(xs[i:j])

这实际上是O(n^2)因为sum,但我们可以通过首先计算前缀总和来轻松解决ps这个问题ps[i] = sum(xs[:i]).然后sum(xs[i:j])很简单ps[j]-ps[i].

这里是上运行的上面的代码的一个例子[2, 5, 1, 1, 2, 2, 3, 4, 8, 2]用[lo, hi] = [3, 6]:

[5]
[5, 1]
[1, 1, 2]
[1, 1, 2, 2]
[1, 2]
[1, 2, 2]
[2, 2]
[2, 3]
[3]
[4]

这会及时运行,输出的大小O(n + t)在哪里t.正如一些人已经注意到的那样,输出可以是大的t = n^2,即如果所有连续的子序列都匹配的话.

如果我们允许以压缩格式(输出对a,b,其中所有子序列都是连续的)写入输出,我们可以得到一个纯O(n)时间算法.

Answer 2

从这个问题开始:找到总和为x的所有连续子序列.我们需要的是类似的东西.

对于每个索引i,我们可以计算从0到i的段的总和,即x.所以,现在的问题是我们需要找到从0到i - 1,有多少段具有从(x - 低)到(x - 高)的和,并且它应该比O(n)快.所以有几种数据结构可以帮助你在O(logn)中做到这一点,它们是Fenwick树和Interval树.

所以我们需要做的是:

• 迭代从0到n的所有索引(n是数组的大小).

• 在索引ith,计算从0到第i个索引的总和x,查询树以获得数字的总出现次数(x - 高,x - 低).

• 将x添加到树中.

所以时间复杂度为O(n log n)

Answer 3

您应该使用简单的动态编程和二进制搜索.要查找计数:

    from bisect import bisect_left, bisect_right

    def solve(A, start, end):
        """
        O(n lg n) Binary Search
        Bound:
        f[i] - f[j] = start
        f[i] - f[j'] = end
        start < end
        f[j] > f[j']

        :param A: an integer array
        :param start: lower bound
        :param end: upper bound 
        :return:
        """
        n = len(A)
        cnt = 0
        f = [0 for _ in xrange(n+1)]

        for i in xrange(1, n+1):
            f[i] = f[i-1]+A[i-1]  # sum from left

        f.sort()
        for i in xrange(n+1):
            lo = bisect_left(f, f[i]-end, 0, i)
            hi = bisect_right(f, f[i]-start, 0, i)
            cnt += hi-lo

        return cnt

https://github.com/algorhythms/LintCode/blob/master/Subarray%20Sum%20II.py

要查找结果而不是计数,您只需要另一个哈希表来存储原始(未排序)f [i] - >索引列表的映射.

干杯.