# runtime O(n^2)
# def two_sum(nums: list[int], target: int):
#     for i in range(0, len(nums) - 1):
#         for j in range(i + 1, len(nums)):
#             a = nums[i]
#             b = nums[j]
#             if a + b == target:
#                 return [i, j]

# time O(n)
# space O(n)  
def two_sum(nums: list[int], target: int):
    seen = {}
    for i in range(len(nums)):
        difference = target - nums[i]
        if difference in seen:
            return [seen[difference], i]
        seen[nums[i]] = i
    return [-1, -1]

def test():
    testcase1 = two_sum([2, 7, 11, 15], 9)
    assert testcase1[0] == 0
    assert testcase1[1] == 1
    assert len(testcase1) == 2

    testcase2 = two_sum([3, 2, 4], 6)
    assert testcase2[0] == 1
    assert testcase2[1] == 2

    testcase3 = two_sum([3, 3], 6)
    assert testcase3[0] == 0
    assert testcase3[1] == 1

if __name__ == '__main__':
    test()

#include <vector>
#include <cassert>
#include <map>

using namespace std;

// time O(n^2)
// space O(1)
// vector<int> twoSum(vector<int>& nums, int target)
// {
//     vector<int> indices = {-1, -1};

//     for (int i = 0; i < nums.size() - 1; i++) {
//         for (int j = i + 1; j < nums.size(); j++) {
//             if (nums.at(i) + nums.at(j) == target) {
//                 indices.at(0) = i;
//                 indices.at(1) = j;
//                 return indices;
//             }
//         }
//     }

//     return indices;
// }

// time O(n)
// space O(n)
vector<int> twoSum(vector<int>& nums, int target)
{
    vector<int> indices = {-1, -1};
    map<int, int> seen;

    for (int i = 0; i < nums.size(); i++)
    {
        int difference = target - nums.at(i);
        map<int, int>::iterator it = seen.find(difference);
        if (it != seen.end()) {
            indices.at(0) = it->second;
            indices.at(1) = i;
            return indices;
        }

        seen.insert({nums.at(i), i});
    }

    return indices;
}

void test()
{
    vector<int> nums = {2, 7, 11, 15};
    auto testcase1 = twoSum(nums, 9);
    assert(testcase1[0] == 0);
    assert(testcase1[1] == 1);

    nums.assign({3, 2, 4});
    auto testcase2 = twoSum(nums, 6);
    assert(testcase2[0] == 1);
    assert(testcase2[1] == 2);

    nums.assign({3, 3});
    auto testcase3 = twoSum(nums, 6);
    assert(testcase3[0] == 0);
    assert(testcase3[1] == 1);
}

int main()
{
    test();
    return 0;
}

func twoSum(nums []int, target int) []int {
	ans := []int{-1, -1}
	var hashMap map[int]int = make(map[int]int)

	for i, num := range nums {
		var difference int = target - num

		if index, ok := hashMap[difference]; ok {
			ans[0] = index
			ans[1] = i
			return ans
		} else {
			hashMap[num] = i
		}
	}

	return ans
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indices = new int[] { -1, -1 };
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (hashMap.containsKey(difference)) {
                indices[0] = hashMap.get(difference);
                indices[1] = i;
                return indices; // or break;
            }
            else {
                hashMap.put(nums[i], i);
            }
        }

        return indices;
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut hashMap = HashMap::new();
        let mut indices = vec![-1, -1];

        for (i, num) in nums.iter().enumerate() {
            let diff = target - num;
            if let Some(&value) = hashMap.get(&diff) {
                indices[0] = value;
                indices[1] = i as i32;
                return indices;
            }
            else {
                hashMap.insert(num, i as i32);
            }
        }

        return indices;
    }
}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        int[] indices = new int[] { -1, -1 };
        Dictionary<int, int> hashMap = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++) {
            int difference = target - nums[i];
            if (hashMap.ContainsKey(difference)) {
                indices[0] = hashMap[difference];
                indices[1] = i;
                break;
            }
            else if (!hashMap.ContainsKey(nums[i])) {
                hashMap.Add(nums[i], i);
            }
        }

        return indices;
    }
}