#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Run-time complexity O(n2)
// Memory complexity O(n)
vector<int> find_indexes(const vector<int>& nums, int sum) {

    unordered_map<int, int> hashmap;
    unordered_map<int, vector<int>> hashmap_index;
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        int current = nums[i];
        for (auto item : hashmap) {
            int complement = sum - current - item.first;
            if (hashmap.count(complement) != 0) {
                if (item.first != complement) {
                    result.push_back(i);
                    result.push_back(hashmap_index[item.first][0]);
                    result.push_back(hashmap_index[complement][0]);
                    return result;
                }
                if (item.first == complement && item.second > 1) {
                    result.push_back(i);
                    result.push_back(hashmap_index[item.first][0]);
                    result.push_back(hashmap_index[item.first][1]);
                    return result;
                }
            }
        }
        ++hashmap[current];
        hashmap_index[current].push_back(i);
    }
    return result;
}

// Run-time complexity O(n2)
// Memory complexity O(n)
vector<int> find_values(const vector<int>& nums, int sum) {

    unordered_map<int, int> hashmap;
    vector<int> result;

    for (int num : nums) {
        for (auto item : hashmap) {
            int complement = sum - num - item.first;
            if (hashmap.count(complement) != 0) {
                if ((item.first == complement && item.second > 1) || item.first != complement) {
                    result.push_back(num);
                    result.push_back(item.first);
                    result.push_back(complement);
                    return result;
                }
            }
        }

        ++hashmap[num];
    }

    return result;
}

void print_vector(const vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
}

int main()
{
    vector<int> v1 = {1, 1, 1, 1};
    int sum1 = 3;

    vector<int> v2 = {6, 1, 2, 4, -2, 2, 6, 7, 10};
    int sum2 = 6;

    print_vector(v1);
    std::cout << std::endl;
    std::cout << sum1 << std::endl << "Values:" << std::endl;
    print_vector(find_values(v1, sum1));
    std::cout << "Indexes:" << std::endl;
    print_vector(find_indexes(v1, sum1));
    std:cout << "---------------" << std::endl;
    print_vector(v2);
    std::cout << std::endl;
    std::cout << sum2 << std::endl << "Values:" << std::endl;
    print_vector(find_values(v2, sum2));
    std::cout << "Indexes:" << std::endl;
    print_vector(find_indexes(v2, sum2));

    return 0;
}