#include <bits/stdc++.h>

using namespace std;

// Problem 1. Two Sum

// Given an array of integers nums and an integer target, return
// indices of the two numbers such that they add up to target.

// You may assume that each input would have exactly one solution, and
// you may not use the same element twice.

// You can return the answer in any order.

class Solution {
public:
    vector<int> twoSum(vector<int> nums, int target)
    {
        map<int,int> mymap;
        vector<int> result;
        
        for (int i=0; i< (int)nums.size(); i++)
        {
            cout << "i: " << i << " target: " << target << " nums[i]: " << nums[i] << " target - nums[i]: " << target - nums[i] << endl;
            auto it = mymap.find(target - nums[i]);
            if(it != mymap.end())
            {
                cout << "found" << endl;
                result.push_back(it->second);
                result.push_back(i);
                return result;
            }
            else
            {
                mymap.insert(make_pair(nums[i],i));
                cout << "insert key(num): " << nums[i] << " val(idx): " << i <<endl;
            }
        }
        return result;
    }
};


int main()
{
    Solution s;
    vector<tuple<int, vector<int>, pair<int,int>>> testCases = {
    // target nums              expected
    // ------ -----------       ------
        {9,   {2,7,11,15},      {0,1}},
        {6,   {3,2,4},          {1,2}},
        {6,   {3,3},            {0,1}},
        {0,   {0,4,3,0},        {0,3}},
        {-8,  {-1,-2,-3,-4,-5}, {2,4}},
        {0,   {-3,4,3,90},      {0,2}},
        {9,   {-10,7,19,15},    {0,2}},
        {0,   {0,3,-3,4,-1},    {1,2}},
        {-19, {-10,-1,-18,-19}, {1,2}},
        {-1,  {0,3,-3,4,-1},    {0,4}},
    };

    for (auto& tc: testCases)
    {
        cout << "target: " << get<0>(tc) << " nums: ";
        for (auto& num: get<1>(tc))
            cout << num << " ";
        cout << endl;
        
        vector<int> indices = s.twoSum(get<1>(tc), get<0>(tc));

        cout << "result: ";
        for (auto& i: indices)
            cout << i << " ";
        cout << " expected: " << get<2>(tc).first << " " << get<2>(tc).second;
        cout << "\n-------------" << endl;
    }
}