谷歌面试：在给定整数数组中找到所有连续子序列，其总和落在给定范围内。我们能比O(n^2)更好吗？

Question

给定一个整数数组和范围（low，high），找到数组中所有连续的子序列，它们的总和在范围内。是否有比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;
}

- user1071840

---

给定一个由全零元素组成、范围为(-1,1)的数组，存在O(n^2)个解，而仅打印这些答案就需要O(n^2)的时间。 - Raymond Chen

@RaymondChen 我认为在他的代码中，他只返回了 count？ - Pham Trung

所有整数都只能是正数吗？还是可以是正数或者负数？ - notbad

@PhamTrung 我在一个网站上看到了这个问题，它说要“查找”所有连续的子序列。我正在进行双重测试以验证我的结果。 - user1071840

@notbad 整数可以是正数或负数。 - user1071840

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)时间复杂度的算法。

- Thomas Ahle

---

我认为即使在 O(1) 空间的情况下，解决这个问题也是可能的。我们可以维护两个和 sum(xs[i:a]) 和 sum(xs[i:b])，而不是计算前缀和数组。当起始位置移动时，即 i 增加时，只需从这两个和中减去相应的值即可。 - wlnirvana

很遗憾，是的。对于负数，我们不能保证序列在b方向上增加，在a方向上减少。 - Thomas Ahle

你能解释一下这个解决方案背后的直觉吗？ - Huey

不适用于负数和零。例如：{5, 10, 2, 3, 5, -5}，范围为[15, 20]。数组中所有元素的总和等于20，但不会被您的算法捕获。不过，您的算法对正整数可以正常工作。 - Saurav Sahu

Answer 2

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

对于每个索引i，我们可以计算从0到i的段的总和，即x。因此，现在的问题是我们需要找到从0到i-1的段中，有多少个总和从（x-low）到（x-high），并且它应该比O（n）更快。因此，有几种数据结构可以帮助您以O（logn）的速度完成此操作，它们是Fenwick树和区间树。

所以我们需要做的是：

• 遍历从0到n（n是数组的大小）的所有索引。

• 在第ith个索引处，计算从0到ith索引，总和为x，在树上查询落在范围（x-high，x-low）内的数字的总出现次数。

• 将x添加到树中。

所以时间复杂度将为O（n log n）

- Pham Trung

---

一个区间树和一个线段树是两个不同的东西。 - John Kurlak

一个区间树不是你想象中的那样。支持你所需操作的数据结构是 Fenwick 树和 Segment 树。 - John Kurlak

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] -> 索引列表的映射。

干杯。

- Daniel

---

好的解决方案！只有 f 可能不需要排序。 - spiralmoon

如果数组包含负数，需要对 f 进行排序。 - Daniel

如果数组包含非负数，则只需求和数组就是单调的，不需要排序即可进行二分查找，但如果数组包含负数，值可能会下降，并且不是单调的，因此需要排序，但我不确定算法的其余部分是否适用于负数。 - FazeL

当数组包含负数时，它无法正常工作。例如，考虑[2，-1]，其中low=-1且high=0。有一个子序列（1,1）其总和为-1，但上述算法将返回0。 - Satvik

@Satvik 如果算法不能处理负数，为什么还需要排序呢？ - Daniele

Answer 4

yes in my opinion it can be in O(n)

struct subsequence
{
int first,last,sum;
}s;

function(array,low,high)
{
int till_max=0;
s.first=0;s.last=0;s.sum=0;
for(i=low;i<high;i++)
{

if(till_max+array[i]>array[i])
{
s.first=s.first;
s.last=i;
till_max+=array[i];
}
else
{
s.first=i;
s.last=i;
till_max=array[i];
}
if(till_max in range)
{
s.sum=till_max;
   printf("print values between first=%d and last=%d and sum=%d",s.first,s.last,s.sum);
}
}
}

- nancy goel

Answer 5

如果只有正数，这是一种可以获得O(nlogn)的方法：

1. Evaluate cumulative sum of array
2. for i  find total sum[j] in (sum[i]+low,sum[i]+high) using binary search
3. Total = Total + count
4. do 3 to 5 for all i

时间复杂度：

Cumulative sum is O(N)
Finding sums in range is O(logN) using binary search
Total Time complexity is O(NlogN)

- Vikram Bhat

---

二分查找？累加和可能不是按排序顺序排列的？ - Pham Trung

@PhamTrung 请注意，这仅适用于正整数。 - Vikram Bhat

Answer 6

如果所有整数都是非负的，那么可以在O(max(size-of-input,size-of-output))时间内完成。这是最优的。

以下是C语言中的算法。

void interview_question (int* a, int N, int lo, int hi)
{
  int sum_bottom_low = 0, sum_bottom_high = 0,
      bottom_low = 0, bottom_high = 0,
      top = 0;
  int i;

  if (lo == 0) printf ("[0 0) ");
  while (top < N)
  {
    sum_bottom_low += a[top];
    sum_bottom_high += a[top];
    top++;
    while (sum_bottom_high >= lo && bottom_high <= top)
    {
      sum_bottom_high -= a[bottom_high++];
    }
    while (sum_bottom_low > hi && bottom_low <= bottom_high)
    {
      sum_bottom_low -= a[bottom_low++];
    }
    // print output
    for (i = bottom_low; i < bottom_high; ++i)
      printf ("[%d %d) ", i, top);
  }
  printf("\n");
}

除了标记为“print output”的最后一个循环之外，每个操作都会执行O(N)次；最后一个循环将为每个打印的间隔执行一次。如果我们只需要计算间隔而不打印它们，则整个算法变为O(N)。

如果允许负数，则很难超越O(N^2)（可能是不可能的）。

- n. m.

Answer 7

使用简单的数据结构，O(NlogN)已足够。

对于连续子序列，我认为它意味着子数组。

我们维护一个前缀和列表，prefix[i] = 前i个元素的总和。如何检查是否存在[low, high]之间的范围？我们可以使用二分搜索。所以，

prefix[0] = array[0]  
for i in range(1, N) 
  prefix[i] = array[i] + prefix[i-1];
  idx1 = binarySearch(prefix, prefix[i] - low);
  if (idx1 < 0) idx1 = -1 - idx1;
  idx2 = binarySearch(prefix, prefix[i] - high);
  if (idx2 < 0) idx2 = -1 - idx2;
  // for any k between [idx1, idx2], range [k, i] is within range [low, high]
  insert(prefix, prefix[i])

我们需要关注的唯一事情是，我们还需要插入新值，因此任何数组或链表都不可以。我们可以使用TreeSet，或者实现自己的AVL树，二分查找和插入都是O(logN)。

- Harry