Задача Twosum с усложнением под range

Question

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

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

target = 9

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

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

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

Answer 1

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

Answer 2

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

У вас есть массив. Вы можете посчитать сумму префиксов в массиве, например 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.

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

Answer 3

Реализация алгоритма от 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)]

БЛОГ НА HUSL

Задача Twosum с усложнением под range

Ответы (3 шт):