Two Sum

The Two-Sum Problem

Conceptually this is a linear search and a linear time algorithm.

// 7 ms (Beats 90%)
// 11.15 MB (Beats 32%)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> diff_idx;
        for (int i = 0; i < nums.size(); ++i) {
            const auto diff = target - nums[i];
            if (diff_idx.find(diff) != diff_idx.end()) {
                return {i, diff_idx[diff]};
            }
            diff_idx[nums[i]] = i;
        }
        return {};
    }
};

# 54 ms (Beats 96%)
# 17.43 MB (Beats 54%)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        diff_idx = {}
        for idx, num in enumerate(nums):
            diff = target - num
            if diff in diff_idx:
                return [idx, diff_idx[diff]]
            diff_idx[num] = idx