Find the two that add up
A reconciliation tool looks for the two entries that together explain a difference.
- Return the two positions, counting from zero, smaller position first.
- If several pairs would work, return the one whose second position comes first.
- No pair means an empty list.
- A value may not be paired with itself, but two equal values at different positions are fine.
pairSummingTo(values: list<int>, target: int) → list<int>
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
std::vector<int> pairSummingTo(std::vector<int> values, int target) {
}Worked examples
| Call | Result |
|---|---|
pairSummingTo(std::vector<int>{2, 7, 11, 15}, 9) | std::vector<int>{0, 1} |
pairSummingTo(std::vector<int>{3, 2, 4}, 6) | std::vector<int>{1, 2} |
pairSummingTo(std::vector<int>{3, 3}, 6) | std::vector<int>{0, 1} |
pairSummingTo(std::vector<int>{1, 2}, 99) | std::vector<int>{} |
Hint
Walk once, and for each value ask whether the number that would complete it has already gone by.
Reference solution in C++
std::vector<int> pairSummingTo(std::vector<int> values, int target) {
std::map<int, int> seen;
for (int j = 0; j < (int) values.size(); j++) {
int v = values[j], need = target - v;
auto it = seen.find(need);
if (it != seen.end()) return {it->second, j};
if (!seen.count(v)) seen[v] = j;
}
return {};
}