Дан массив целых чисел, нужно найти непустой подотрезок (непрерывную подпоследовательность) с заданной суммой X, либо сказать, что это невозможно.
Для найденного отрезка (если он существует) следует выдать на выход индексы его концов.
Решение:
Частичные суммы, далее два варианта:
1) Сортировка / std::map, решение за O(nlogn)
2) Хешмапа, решение за O(N)
unordered_map<long long, int> sum_map;
sum_map[0] = -1;
long long sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
auto it = sum_map.find(sum - X);
if (it != sum_map.end()) {
return {it->second + 1, i};
}
if (!sum_map.count(sum)) {
sum_map[sum] = i;
}
}
return {-1, -1};
Что нужно учитывать:
1) В массиве могут быть отрицательные числа
2) Подотрезок должен быть непустой
Хорошо, если вы скажете про переполнение и что перфиксная сумма может не поместиться в int
Итоговое решение O(N)
@algoses