/*
   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. 

   Example 1:
   Input: nums = [2,7,11,15], target = 9
   Output: [0,1]
   Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
   Example 2:
   Input: nums = [3,2,4], target = 6
   Output: [1,2]
   Example 3:
   Input: nums = [3,3], target = 6
   Output: [0,1]
 

   Constraints:

   2 <= nums.length <= 104
   -109 <= nums[i] <= 109
   -109 <= target <= 109
   Only one valid answer exists.
   Follow-up: Can you come up with an algorithm that is less than
   O(n2) time complexity?
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    vector<int> twoSum(const vector<int>& nums, int target)
    {
        // map of (target - number)  to index of number in nums vector
        unordered_map<int,int> twoSumMap;
        
        for (int curr_index = 0; curr_index < (int)nums.size(); curr_index++)
        {
            int curr_num = nums[curr_index];
            int difference = target - curr_num;
            
            if (twoSumMap.contains(difference))
            {
                return vector<int>{twoSumMap[difference], curr_index};
            }            
            else
            {
                twoSumMap[curr_num] = curr_index;
            }
        }
        return vector<int>{};
    }
};

int main(void)
{
    vector<tuple<vector<int>, int, vector<int>>> testCases = {
        // input arr      target
        { {2,7,11,15},     9, {0,1} },
        { {2,7,11,15,15}, 30, {3,4} },
        { {2,7,11,15},    17, {0,3} },
        { {-7,-2,11,15},  -9, {0,1} },
        { {3,3},           6, {0,1} },
    };

    Solution s;
    
    for (const auto& testCase: testCases)
    {
        vector<int> result = s.twoSum(get<0>(testCase), get<1>(testCase));
        
        string input("input: {"); for(auto& i: get<0>(testCase)) input += to_string(i) + ","; input += "}";
        string res  ("result: {"); for(auto& i: result) res += to_string(i) + ","; res += "}";
        string target("target: " + to_string(get<1>(testCase)));

        cout << setw(25) << left << input << setw(15) << left << target << setw(20) << left << res << endl;

        EXPECT_EQ(result, get<2>(testCase));
    }
}