сумма сложности

Question

предположим, что вам дано

A=[2, 5, 7, 2, 6, 7, 6, 5, 6, 5].  

Sum=[0, 0, 0, 12, 0, 8, 7, 28, 5, 6].

использовать O (n) дополнительное пространство и ** должно выполняться за O (n) время ****.

Answer 1

Если вам разрешено использовать std::unordered_map, вы можете использовать что-то вроде:

auto IntervalSum(const std::vector<int>& A)
{
    std::vector<int> res;
    std::unordered_map<int, int> m;
    int sum = 0;

    for (auto e : A) {
        sum += e;
        if (auto [it, inserted] = m.emplace(e, sum); !inserted) {
            res.push_back(sum - e - it->second);
            it->second = sum;
        } else {
            res.push_back(0);
        }
    }
    return res;
}

Демо

Конструкция C ++ 17

if (auto [it, inserted] = m.emplace(e, sum); !inserted) {

может быть переписан в предыдущей версии (C ++ 11 / C ++ 14):

auto p = m.emplace(e, sum);
auto it = p.first;
bool inserted = p.second;
if (!inserted) {