Поиск индексов двух элементов с требуемой суммой

Условие

Дан массив целых чисел arr и целое число sumTarget. Требуется вернуть индексы двух элементов, которые в сумме дают sumTarget.

Пример 1: Input: arr = [2,7,11,15], sumTarget = 9 Output: [0,1] Explanation: arr[0] + arr[1] == 9 → возвращаем [0, 1]

Пример 2: Input: arr = [3,2,4], sumTarget = 6 Output: [1,2]

Пример 3: Input: arr = [3,3], sumTarget = 6 Output: [0,1]

class Solution {
public:
    vector<int> twoSum(vector<int>& arr, int sumTarget) {
    }
};

Ответ

Обходите массив и храните индексы уже встреченных значений. Для текущего элемента сначала ищите дополнение до sumTarget, затем сохраняйте сам элемент — так он не используется дважды.

Для обычного 32-битного int и индексов, помещающихся в int:

std::vector<int> twoSum(std::vector<int>& arr, int sumTarget) {
    std::unordered_map<long long, int> seen;
    for (std::size_t i = 0; i < arr.size(); ++i) {
        const long long needed = static_cast<long long>(sumTarget) - arr[i];
        const auto found = seen.find(needed);
        if (found != seen.end()) return {found->second, static_cast<int>(i)};
        seen.emplace(arr[i], static_cast<int>(i));
    }
    return {};
}

Для [3, 3] и суммы 6 возвращается [0, 1]. При отсутствии пары возвращается пустой vector. Время в среднем O(n), память O(n); расширенный тип дополнения предотвращает переполнение при вычитании двух int.