#include <fmt/ranges.h>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution
{
public:
    // the basic brute force version
    vector<int> twoSumBF(vector<int> &nums, int target)
    {
        for (auto it1 = nums.begin(); it1 != nums.end(); ++it1) {
            auto it2 = std::find(it1 + 1, nums.end(), target - *it1);
            if (it2 != nums.end())
                return {static_cast<int>(it1 - nums.begin()), static_cast<int>(it2 - nums.begin())};
        }
        return {};
    }

    // One-pass has table
    vector<int> twoSumOnePassHash(vector<int> &nums, int target)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (hash.contains(complement)) {
                return {i, hash[complement]};
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

int main()
{
    Solution sol;

    // test cases
    std::pair<vector<int>, int> test1 = {{11, 15, 2, 7}, 9};
    std::pair<vector<int>, int> test2 = {{3, 2, 4}, 6};
    std::pair<vector<int>, int> test3 = {{3, 3}, 6};

    for (auto [nums, target] : {test1, test2, test3}) {
        fmt::print("nums: {} target: {} Output: {}\n",
                   fmt::join(nums, ", "),
                   target,
                   fmt::join(sol.twoSumOnePassHash(nums, target), ", "));
    }
}