Ask the past before adding the present
Solve two-sum safely and choose a container by required operations.
Two different positions, possibly equal values
For each current value x, a partner must equal target − x. Search only values from earlier positions, then record x. This order prevents a single occurrence from pairing with itself. Two separate 5s can sum to 10; one 5 cannot.
The invariant before the current query is that the container represents exactly the already processed positions. A found complement proves a valid earlier partner. Conversely, every valid pair is detected when its later endpoint is processed.
Type and input contracts still matter
Use long long for target, x, and their difference. Even when individual values fit int, subtraction may exceed its range. Continue consuming the stated input after finding a pair so the same routine can be used inside a multi-case program.
The hash version uses average O(n) work and O(d + b) storage for d keys and b buckets; its worst-case time can be O(n²). A set or map gives O(n log(n + 1)) key operations with deterministic ordered-container bounds. Because this task asks only existence, a set of prior values is sufficient too.
// Complete C++23 program. Input: n target, followed by n values.
#include <iostream>
#include <unordered_map>
int main() {
int n;
long long target;
std::cin >> n >> target;
std::unordered_map<long long, int> seen;
bool possible = false;
for (int i = 0; i < n; ++i) {
long long x;
std::cin >> x;
if (seen.contains(target - x)) possible = true;
++seen[x];
}
std::cout << (possible ? "YES" : "NO") << '\n';
}Choose operations, then count all work
Distinct nearby-key queries suggest set; selecting repeated items suggests multiset; per-key information in order suggests map; exact-key information without ordering may suit unordered_map. Static sorted data may need only a vector. A data structure earns its place by making the needed operations efficient.
Do not hide a linear iterator walk, copied container, long string comparison, duplicate count, or output pass inside a “logarithmic lookup” estimate. A const-reference helper avoids O(d) copying per call.
Why does inserting x before searching target − x falsely accept input [5] with target 10?
Turn the idea into code
Trace target 10 for [5] and for [5, 1, 5, 8]. State exactly when the successful pair appears.
Give me a hint
Write the set of prior keys immediately before each lookup.
Show the explained solution
The one-value case finds no prior 5 and returns NO. In the longer input, the first 5 misses, 1 misses complement 9, and the second 5 finds the earlier 5. The algorithm returns YES while still reading the remaining 8.
Your notes
Mark complete when you can explain it yourself.