LeetCode: Two Sum Solution

Approach: Hash table

Use hash table to reduce the query time complexity for target - num

Implementation

1var twoSum = function (nums, target) {
2  const elLastIdxMap = nums.reduce(
3    (acc, el, idx) => acc.set(el, idx),
4    new Map()
5  )
6
7  for (const [idx, num] of nums.entries()) {
8    const rest = target - num
9    if (elLastIdxMap.has(rest) && elLastIdxMap.get(rest) !== idx) {
10      return [idx, elLastIdxMap.get(rest)]
11    }
12  }
13}

References

Original problem

Similar problems

3Sum

4Sum

Two Sum II - Input Array Is Sorted

Two Sum III - Data structure design

Subarray Sum Equals K

Two Sum IV - Input is a BST

Two Sum Less Than K

Max Number of K-Sum Pairs

Count Good Meals

Count Number of Pairs With Absolute Difference K

Number of Pairs of Strings With Concatenation Equal to Target

Find All K-Distant Indices in an Array

First Letter to Appear Twice

Number of Excellent Pairs

Number of Arithmetic Triplets

Node With Highest Edge Score

Check Distances Between Same Letters

Find Subarrays With Equal Sum

Largest Positive Integer That Exists With Its Negative

Number of Distinct Averages