По заданному целочисленному массиву найдите начальные индексы смежных подпоследовательностей длины L, чтобы их сумма равнялась S

Question

Учитывая массив целых положительных чисел, значения которого приведены в [1, 8], я хочу найти начальные индексы смежных подпоследовательностей длины L, сумма которых равна S. Этот запрос можно обозначить как Q . Пример приведен ниже:

A: [3, 2, 3, 1, 2, 1, 3, 1, 1, 6, 3, 3, 3, 2, 3, 1, 1, 3]  
Q< 3, 5 > : [5, 6, 14, 15] ;  
Starting at index 5:  {1, 3, 1},  
Starting at index 6:  {3, 1, 1},  
Starting at index 14: {3, 1, 1},  
Starting at index 15: {1, 1, 3}

Q< 4, 9 > : [0, 12] ;  
Starting at index 0:  {3, 2, 3, 1},  
Starting at index 12: {3, 2, 3, 1}  

Результат запроса может быть вычислен тривиально за O (n) раз. Есть ли способ найти эти индексы за O (1) или O (log n), предварительно обработав массив? Пространственная сложность структуры данных предварительно обработанного массива предпочтительно не должна превышать O (n).

Answer 1

Вы можете построить массив суммирования, чтобы найти сумму L смежных элементов за O (n) времени.

A: [3,2,3,1,2,1,3,1]
S: [3,5,8,9,11,12,15,16]

Теперь для каждого элемента i в A вы можете найти его суммирование по S [i + L] -S [i]. Общая сложность будет O (n).

    int n = 9;
    int a[] = {0,3,2,3,1,2,1,3,1};
    int l = 3;
    int sum = 5;
    int s[] = new int[n];

    s[0] = a[0];
    for(int i=1;i<n;i++)
    {
        s[i] = a[i]+s[i-1];
    }
    for(int i=0;i<n-l;i++)
    {

        int cur = s[i+l]-s[i];

        if(cur == sum)
        {
            System.out.println(cur);
        }
    }