Google Interview: найдите всю прилежащую подпоследовательность в заданном массиве целых чисел, сумма которых попадает в заданный диапазон. Можем ли мы лучше, чем O (n ^ 2)?

Ответ 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).

Ответ 2

Начиная с этой проблемы : найдите все смежные подпоследовательности, которые суммируются с x. Нам нужно что-то подобное.

Для каждого индекса я мы можем вычислить сумму от 0 до i, которая равна x. Итак, теперь проблема состоит в том, что нам нужно найти от 0 до я - 1, сколько сегментов имеет сумму от (x - low) до (x - high), и оно должно быть быстрее, чем O (n). Таким образом, несколько структур данных помогут вам сделать это в O (logn), которые Fenwick tree и Дерево интервала.

Так что нам нужно сделать:

• Итерация по всему индексу от 0 до n (n - размер массива).

• В индексе ith, вычисляя, начиная с 0 до i-го индекса, сумма x запрашивает дерево, чтобы получить общее количество чисел попадания в диапазон (x - высокий, x - низкий).

• Добавьте x в дерево.

Таким образом, временной сложностью будет O (n log n)

Ответ 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] → списка индексов.

Приветствия.

Ответ 4

Здесь вы можете получить 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)

Ответ 5

Если все целые числа неотрицательны, то это можно сделать в 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");
}

За исключением последнего цикла с надписью "вывод печати", каждая операция выполняется O (N) раз; последний цикл выполняется один раз для каждого отпечатанного интервала. Если нам нужно только подсчитать интервалы и не печатать их, весь алгоритм станет O(N).

Если отрицательные числа разрешены, то O(N^2) трудно превзойти (может быть невозможно).

Ответ 6

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);
}
}
}