Google访谈:在给定的整数数组中查找所有连续的子序列，这些整数的总和在给定的范围内.我们可以做得比O(n ^ 2)好吗? [英] Google Interview: Find all contiguous subsequence in a given array of integers, whose sum falls in the given range. Can we do better than O(n^2)?

问题描述

给出一个整数数组和一个范围(低，高)，找到所有数组中连续的子序列，其总和在范围内.

Given an array of Integers, and a range (low, high), find all contiguous subsequence in the array which have sum in the range.

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

Is there a solution better than O(n^2)?

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

I tried a lot but couldn't find a solution that does better than O(n^2). Please help me find a better solution or confirm that this is the best we can do.

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

This is what I have right now, I'm assuming the range to be defined as [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;
}

推荐答案

O(n)时间解决方案:

您可以将两个指针"的概念扩展为问题的精确"版本.我们将维护变量 a 和 b ，以使所有间隔的形式为 xs [i，a)，xs [i，a + 1)，...，xs [i，b-1)的总和在搜寻范围 [lo，hi] .

You can extend the 'two pointer' idea for the 'exact' version of the problem. We will maintain variables a and b such that all intervals on the form xs[i,a), xs[i,a+1), ..., xs[i,b-1) have a sum in the sought after range [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])

由于 sum ，这实际上是 O(n ^ 2)，但是我们可以通过首先计算前缀和 ps 使得 ps [i] = sum(xs [:i]).那么 sum(xs [i:j])就是 ps [j] -ps [i] .

This is actually O(n^2) because of the sum, but we can easily fix that by first calculating the prefix sums ps such that ps[i] = sum(xs[:i]). Then sum(xs[i:j]) is simply 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 .

This runs in time O(n + t), where t is the size of the output. As some have noticed, the output can be as large as t = n^2, namely if all contiguous subsequences are matched.

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

If we allow writing the output in a compressed format (output pairs a,b of which all subsequences are contiguous) we can get a pure O(n) time algorithm.

这篇关于Google访谈:在给定的整数数组中查找所有连续的子序列，这些整数的总和在给定的范围内.我们可以做得比O(n ^ 2)好吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！