Tom on the Internet
← Back

Two Sum

easy
Array Hash Table

<Code />

function twoSum(nums, target) {
    let seen = new Map();
    for (let i = 0; i < nums.length; i++) {
        let x = target - nums[i];
        if (seen.has(x)) {
            return [seen.get(x), i];
        }
        seen.set(nums[i], i);
    }
}

Thoughts

Another simple problem, but definitely one that would have tripped be up at first. It's easy to think you need to compare every element with every other element (O(n^2)), but you can do it in O(n) time by using a hash map to store the indices of the elements you've seen so far.