Two Sum

There are again a bunch of ways to do it. The naive approach would be to iterate 2 times over the array and check if they add up to the target number.

Naive Approach

std::vector<int> two_sum(std::vector<int> list, int target) {
    for (int i = 0; i < list.size(); i++) {
        for (int j = i + 1; j < list.size(); j++) {
            if (list[i] + list[j] == target) return {std::min(i, j), std::max(i, j)};
        }
    }
    return {};
}

def two_sum(list: List[int], target: int) -> List[int]:
    for i in range(0, len(list)):
        for j in range(i + 1, len(list)):
            if list[i] + list[j] == target:
                return [min(i, j), max(i, j)]

    return []

Optimized Approach (Hash Map)

If we want to reduce the time complexity we can use a hashmap. We iterate through the list and calculate the complement of the target t - the current list value list[i]. Then we check if that complement is somewhere in the hashmap, if so we return it.

std::vector<int> two_sum(std::vector<int> list, int target) {
    std::unordered_map<int, int> complementMap{};

    for (int i = 0; i < list.size(); i++) {
        int complement = target - list[i];
        std::cout << "Complement is " << complement << std::endl;
        if (complementMap.find(complement) != complementMap.end()) {
            return {std::min(complementMap[complement], i),
                    std::max(complementMap[complement], i)};
        }
        complementMap[list[i]] = i;
    }

    return {};
}

def two_sum(list: List[int], target: int) -> List[int]:
    complement_map = {}
    for i in range(len(list)):
        c = target - list[i]
        if c in complement_map:
            return [min(complement_map[c], i), max(complement_map[c], i)]
        complement_map[list[i]] = i
    return []