MiddleКодЧастоЕщё не отвечали
Найти подотрезок с суммой X (с отрицательными числами)
Дан массив целых (возможно, отрицательных) и цель X. Найдите любой непустой непрерывный подотрезок с суммой X и верните его индексы [start, end], или {-1, -1}, если такого нет.
Требования:
- O(n) по времени.
- Из-за отрицательных чисел скользящее окно не работает.
std::pair<int,int> subarrayWithSum(const std::vector<int>& a, long long X) {
// ваш код здесь
}Допишите реализацию.
Идите по массиву, накапливая префиксную сумму P, с хеш-таблицей «префикс → ранний индекс», засеянной 0 → -1. На каждом j, если P - X есть в таблице, подотрезок после того индекса до j даёт сумму X. Отрицательные числа исключают окно, поэтому таблица даёт O(n).
- ✗Использовать скользящее окно при отрицательных числах, что ломает монотонность суммы
- ✗Забыть засеять
0 → -1, из-за чего подотрезок с начала пропускается - ✗Допустить переполнение префиксной суммы в
intна больших входах
- →Как упростился бы подход, если бы все числа гарантированно были неотрицательными?
- →Почему запись-затравка
0 → -1необходима?
Оглавление
Задача
Найдите непрерывный подотрезок с суммой X (числа могут быть отрицательными) за O(n).
Решение
#include <vector>
#include <unordered_map>
#include <utility>
std::pair<int,int> subarrayWithSum(const std::vector<int>& a, long long X) {
std::unordered_map<long long, int> firstIdx;
firstIdx[0] = -1; // пустой префикс
long long prefix = 0;
for (int j = 0; j < static_cast<int>(a.size()); ++j) {
prefix += a[j];
auto it = firstIdx.find(prefix - X);
if (it != firstIdx.end()) return {it->second + 1, j};
firstIdx.emplace(prefix, j); // только ранний индекс
}
return {-1, -1};
}Ключевые моменты
- Ищем
prefix - Xсреди ранее виденных префиксов — это даёт O(n). - Затравка
0 → -1ловит подотрезок, начинающийся с нуля. - При отрицательных числах окно не годится.
Оглавление
