JuniorКодЧастоЕщё не отвечали
Индекс равновесия, где сумма слева равна сумме справа
Найдите индекс i массива целых чисел такой, что сумма элементов строго слева от i равна сумме элементов строго справа. Значения могут быть отрицательными; если такого индекса нет, верните -1.
Требования:
префиксных сумм.
- O(n) время, O(1) дополнительной памяти — без вложенных циклов и без массива
int equilibriumIndex(const std::vector<int>& a) {
// ваш код здесь
}Допишите реализацию.
Сначала посчитайте общую сумму. Затем за один проход ведите текущую левую сумму; на индексе i правая сумма равна total - left - a[i]. Когда left == total - left - a[i], верните i. Один проход после подсчёта суммы — O(n) время и O(1) дополнительной памяти. Верните -1, если совпадений нет.
- ✗Пересчитывать правую сумму с нуля на каждом индексе, получая O(n²)
- ✗Забывать, что
a[i]не относится ни к одной стороне, и неверно выводить правую сумму - ✗Не обрабатывать пустой массив или возвращать неверное значение-маркер, когда баланса нет
- →Почему вычитание
a[i]из общей суммы даёт ровно сумму правой стороны? - →Как найти все индексы равновесия, а не только первый?
Оглавление
Задача
Найдите индекс, где сумма слева равна сумме справа (значения могут быть отрицательными), за O(n) и O(1) памяти; иначе -1.
Решение
#include <vector>
#include <numeric>
int equilibriumIndex(const std::vector<int>& a) {
long long total = std::accumulate(a.begin(), a.end(), 0LL);
long long left = 0;
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
long long right = total - left - a[i]; // a[i] не входит ни в одну сторону
if (left == right) return i;
left += a[i];
}
return -1;
}Ключевые моменты
- Правая сумма выводится из общей:
right = total - left - a[i], без второго прохода. a[i]исключается из обеих сторон — частая ошибка забыть это вычитание.- O(n) время, O(1) память;
long longзащищает от переполнения суммы.
Оглавление
