Given an array of $n$ elements, you are asked to find two values which sum to $x$.

Main Idea

Let's start by iterating over the first value in $\mathcal{O}(n)$ time. Given one value, $a$, the other value must be $x - a$ unless $a > x$ (in which case $a$ cannot be a valid first value).

So the question reduces to, given some value $a$, does some other value $x - a$ exist?

Using a Map

One idea that comes to mind would be to used a boolean array to store the values. Unfortunately, since $a_i \leq 10^9$, this approach isn't feasible.

However, we can store the values in an (un)ordered map which maps each value to an index, and use the .count method to check whether a value exists, and return the corresponding index if it does.

To be careful not to count the same index twice, we'll add values to the map as we iterate through it, so at some index $i$ you only consider values with index $j < i$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first