24 Jun 2023•C++ / Python / TypeScript•Easy

Two Sum

find two indices whose values sum to target using hash map for O(n) lookup.

use hash map to store number → index mapping. for each number, check if complement (target - num) exists in map. if found, return both indices.

single pass through array: check complement before adding current number to map. this handles cases where same number appears twice.

complexity

O(n) time for single pass, O(n) space for hash map. classic hash map problem.

Solution files

Python•two sum/solution.py

Solution file content could not be loaded.

Python•two-sum/synced-solution.py

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in seen:
                return [seen[diff], i]
            seen[n] = i
        return []

C++•two-sum/synced-solution.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> seen;
        for (int i = class="syntax-number">0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (seen.count(diff)) return {seen[diff], i};
            seen[nums[i]] = i;
        }
        return {};
    }
};

TypeScript•two-sum/synced-solution.ts

function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();
    for (let i = class="syntax-number">0; i < nums.length; i++) {
        const diff = target - nums[i];
        if (seen.has(diff)) return [seen.get(diff)!, i];
        seen.set(nums[i], i);
    }
    return [];
}