CSES - Sum of Three Values

Time Complexity: $\mathcal{O}(N^2)$

This problem is an extension of the two sum problem except now with three values. We can set the third pointer to a certain value in the array and then the problem becomes the two sum problem discussed earlier in this module.

First we'll sort the array. Then we'll loop through all possible values for the third pointer and check if all three pointers add up to the target amount, $x$, while having distinct positions. We can maintain the original positions of all values by storing the pairs {a[i],i}.

1#include <bits/stdc++.h>
2using namespace std;
3
4int main(){
5    ios_base::sync_with_stdio(0); cin.tie(0);
6    int n,x; cin >> n >> x;
7    vector<pair<int, int>> arr;
8    for(int i = 1; i <= n; i++){
9        int a; cin >> a;
10        pair<int, int> p; p.first = a; p.second = i;