2

Дан список целых чисел и число-цель. Нужно найти такой range, чтобы сумма его элементов давала число-цель.

elements = [1, -3, 4, 5]

target = 9

result = range(2, 4) # because elements[2] + elements[3] == target

Хочется понять основную идею, чем тут можно дополнительно воспользоваться, чтобы решить за линейное время.

Самое очевидное решение, это - брать элемент и суммировать все последующие элементы до конца и проверять было ли в процессе значение равное target, но тогда это будет довольно долго, потому что N итераций с первого элемента, N - 1 итераций со второго элемента и т.д, получается примерно квадратичная. А как можно лучше?

3 ответа 3

6

Алгоритм простой как два рубля.

У вас есть массив. Вы можете посчитать сумму префиксов в массиве, например SumX1 и SumX2 - будут суммы от 0 до X1 и от 0 до X2 (где X2 > X1)

Тогда сумма итервала между X1 и X2 будет равна SumX2-SumX1.

Наша задача найти такие суммы интервалов SumX2-SumX1 = target.

Так как в каждый момент времени мы вычисляем SumX2 (все суммы до X2 уже вычислены), то немного переделав урвнение SumX2-SumX1 = target ==> SumX2-target = SumX1 мы понимаем, какую уже вычисленную сумму искать в мапе - ту, которая равнв SumX2-target.

Код на C# будет выглядеть как то так

void printIntervals(int[] data, int target)
{
    var prefixSums = new Dictionary<int, List<int>>();

    int sum = 0;
    for (int i = 0; i < data.Length; i++)
    {
        sum += data[i];

        if (sum == target) Console.WriteLine($"0 - {i}");
        if (prefixSums.ContainsKey(sum - target))
        {
            var indices = prefixSums[sum - target];
            foreach (var ind in indices) Console.WriteLine($"{ind + 1} - {i}");
        }
        if (!prefixSums.ContainsKey(sum)) prefixSums[sum] = new List<int>() { i };
        else prefixSums[sum].Add(i);
    }
}

Проверка

printIntervals(new int[] {1, -3, 4, 5}, 9);

Вывод

2 - 3

Так и получается, сумма в интервале [2,3] (или интервале [2,4)) равна 9.

Поъожая задача на литкоде, там в разборе даже гифка есть =)

3
  • 1
    Надо картинки нарисовать, так всё-равно никак не могу понять я лично ))
    – CrazyElf
    5 апр в 13:28
  • 1
    @CrazyElf добавил картинку ))
    – tym32167
    5 апр в 13:33
  • Спасибо, примерно понял) 5 апр в 13:33
2

Реализация алгоритма от tym32167 на Python. Вдруг кому пригодится.

from collections import defaultdict
from itertools import accumulate


def printIntervals(elements: list[int], target: int) -> list[tuple]:
    sum_dict: defaultdict = defaultdict(list[int])
    result_list: list[tuple] = list()

    # Суммируем элементы списка по нарастающей и сохраняем в словаре
    # ключ: сумма, значение: список индексов для каждой суммы
    for id_to, sum_accum in enumerate(accumulate(elements)):
        
        if sum_accum == target:
            result_list.append((0, id_to))
    
        for id_from in sum_dict.get((sum_accum - target),[]):
            result_list.append((id_from + 1, id_to))
    
        sum_dict[sum_accum].append(id_to)

    return(result_list)


result = printIntervals([1, -3, 4, 5], 9)
print(result)  # [(2, 3)]

result = printIntervals([1, -1, 4, 3, 2, 1, -3, 4, 5, -5, 5], 9)
print(result)  # [(0, 4), (2, 4), (1, 5), (4, 8), (4, 10), (7, 8), (7, 10)]
2
  • Важная часть алгоритма (что этого, что для 2Sum проблемы) в том, что мы для каждой суммы сначала ищем ей пару, а потом уже добавляем её в хешмапу, чтобы не париться, если наша же сумма сама себе будет парой. Такое может случиться, например, при target=0.
    – tym32167
    5 апр в 19:52
  • Спасибо за замечание. Код исправил. Теперь target=0 отрабатывает корректно. 5 апр в 21:05
1

Считать кумулятивные суммы (от начала до текущего элемента), складывать их в мап (словарь), для каждой суммы S проверять, нет ли в мапе значения S-target

9
  • Ну и проверять, не равны ли S и target
    – tym32167
    5 апр в 12:40
  • @tym32167 Можно в словарь 0 занести, чтобы отдельно проверку не делать
    – MBo
    5 апр в 12:41
  • Как вариант, согласен :)
    – tym32167
    5 апр в 12:41
  • Но ведь всё-равно придётся для каждого N-го элемента обновлять все текущие кумулятивные суммы, от всех элементов начиная от 1-го до N-1-го, то есть всё-равно O(n^2) будет?
    – CrazyElf
    5 апр в 13:06
  • 1
    @CrazyElf накатал код =)
    – tym32167
    5 апр в 13:24

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.