谷歌面试:在给定的整数数组中查找所有连续的子序列，其和在给定范围内.我们能比 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])

这实际上是 O(n^2) 因为 sum，但我们可以通过首先计算前缀和 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]:

Here is an example of running the above code on [2, 5, 1, 1, 2, 2, 3, 4, 8, 2] with [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.

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