Подмассив массива, сумма элементов которого равна K

Cellarie · Регистрация: 23.02.2019

Студворк — интернет-сервис помощи студентам

Здравствуйте! Не могу понять, какой алгоритм используется для решения задачи, подскажите, пожалуйста!
Условие задачи:
Дан массив чисел размера n $https://www.cyberforum.ru/cgi-bin/latex.cgi?(n\leq {10}^{5})$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi? \left| {a}_{i}\right|\leq {10}^{9}$ и число k $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\left|k\right|\leq {2*10}^{9})$ . Необходимо найти границы подмассива (l, r) последовательных элементов этого массива, сумма которых будет равна n.
Например, при n=10, n={4, -3, 17, 5, 4, 1, 0, -21, -1, 6}, k=3, ответом будет {-3, 17, 5, 4, 1, 0, -21}, то есть (1, 7), если нумеровать элементы массива с нуля. В голову не приходят никакие варианты решения кроме полного перебора, который тут не подходит. Какой алгоритм используется для решения этой задачи? Буду благодарен за любую помощь.

@salam · 24.02.2019, 16:01

надо подсчитать частичные суммы и складывать их в контейнер, поддерживающий быстрый поиск, например, хэш-таблицу.

@VTsaregorodtsev · 24.02.2019, 19:56

Сообщение от Cellarie

сумма которых будет равна n.

Опечатка. Не n - а k.

Cellarie · 25.02.2019, 00:52 **[ТС]**

Да, не заметил опечатку.

@VTsaregorodtsev · 25.02.2019, 20:37

Cellarie, Вычислительная сложность O(n^2) устроит? Будут найдены все подходящие последовательности (т.е. всех возможных длин), имеющие нужное значение суммы своих элементов.
Ваш полный перебор - это, как я понимаю, O(n^3)? Будет тот же полный перебор - только оптимизированный

под некое арифметическое свойство целых чисел (отсутствующее у компьютерных чисел с плавающей точкой - ну, так Вам же целые обрабатывать в этой задаче, а не плавучку).

И никаких контейнеров и хэшей, как советовали

Тем более, что за O(n) задача не решается, а для O(1) придётся ждать наступления эры квантовых компьютеров

@salam · 26.02.2019, 01:17

1. O(n^2) не устроит, ибо n <= 10^5.
2. за O(n) (правда, ожидаемое, ибо хэш таблица - вероятностная структура данных) решается.
3. решается еще, например, за O(nlogn) примерно также, как и с таблицей, только с кучей дополнительных телодвижений по предподсчету заранее всех частичных сумм, их сортировки и заполнению по ходу дела вместо хэш-таблицы дерева отрезков, использующего отсортированные частичные суммы в качестве "сжатых координат".

@Shamil1 · 26.02.2019, 10:13

Вот алгоритм, который предложил salam:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Main()
{
    int[] a = new int[] { 4, -3, 17, 5, 4, 1, 0, -21, -1, 6 };
    Console.WriteLine($"{Solve(a, 3)}"); //(1, 7)
}
 
(int,int)? Solve(int[] a, int k)
{
    var m = new Dictionary<int, int>(a.Length);
    for(int i = 0, s = 0; i < a.Length; i++)
    {
        s += a[i];
        if(s == k)
            return (0, i);
        if(m.TryGetValue(s - k, out int j))
            return (j + 1, i);
        m[s] = i;           
    }
    return null;
}

Куда уж проще? Сложность будет зависеть от реализации словаря.

@VTsaregorodtsev · 27.02.2019, 23:03

Сообщение от Shamil1

Вот алгоритм, который предложил salam:

Ну и где там итоговое О(n)? У TryGetValue разве О(1) будет?
И не забывайте приплюсовать время создания словаря.

Сообщение от salam

O(n^2) не устроит, ибо n <= 10^5.

Меня почему-то устраивает

Ибо итерация внутреннего цикла - дешёвенькая. Один минус, один плюс, и сравнение с искомой целочисленной переменной k. Т.е. никаких поисков на внутреннем цикле.
Для n=10^5 срабатывает мгновенно. Ищет, напоминаю, ВСЕ решения (т.е. подмассивы длин от 1 до n).
Вот для 10^6 - да, уже несколько секунд.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Solve(int *A, int Length, int k)
{
    for ( int i=1 ; i<Length ; i++ ) { //будет задавать длину проверяемой (под)последовательности
        int j, Summ=0;
        //считаем сумму элементов для первой позиции окна
        for ( j=0 ; j<i ; j++ )
            Summ+=A[j];
        if ( Summ==k )
            PrintIndexes(j-i+1,j);
        for ( ; j<Length ; j++ ) {
            //при сдвиге окна добавляем возникший справа элемент и вычитаем
            //элемент, бывший крайним слева на предыдущей позиции окна. И вуаля -
            //оказывается посчитанной сумма ВСЕХ элементов в новом положении окна ;)
            Summ+=A[j]-A[j-i];
            if ( Summ==k )
                PrintIndexes(j-i+1,j);
        }
    }
}
 
//Функцию PrintIndexes желающие сюда напишут сами

Куда уж проще? (это специально написанные комментарии - а то народ не поймёт идею - визуально раздувают код, а если комментарии выкинуть...)
И сложность вообще не зависит от реализации никаких "левых" коллекций

Добавлено через 36 минут