Question

LeetCode Link | 1. Two Sum | Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

Constrains

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Solution Approach

Method: Unordered Map / Hash Table

Constrains

  • Key, Value

When we need to check if an element has appeared before or if an element is in a set, we should immediately think of using hash methods.

Let’s also look at the limitations of using arrays and sets for hashing.

Array - The size of an array is limited, and if there are few elements but the hash values are too large, it will lead to a waste of memory space.

Set - A set is a collection that can only contain keys. In problems like “two-sum”, where we not only need to check if difference value (x) exists but also need to record the index of this number (y) because we need to return the indices of x and y, a set is also not suitable.

Concept Explanation

In this problem, we need a collection to store the elements we have traversed. Then, as we iterate through the array, we inquire with this collection whether a certain element has been traversed, that is, whether it appears in this collection. Therefore, we should consider using hash methods.

For this problem, we need to know not only whether an element has been traversed but also the corresponding index of the element. Therefore, a key-value structure is necessary, where the key stores the element and the value stores the index. Using a map is perfectly suitable for this purpose.

While iterating through the array, you only need to query the map to see if there is a value that matches the current element being traversed. If there is a match, you’ve found the corresponding pair. If not, you put the current element into the map, because the map stores the elements we have accessed.

Code

  • Time complexity: O(n)
  • Space complexity: O(n)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
function twoSum(nums: number[], target: number): number[] {
    const storeMap: Map<number, number> = new Map();
    for (let i = 0; i < nums.length; i++) {
        let diff = target - nums[i];
        if (storeMap.has(diff)) {
            return [storeMap.get(diff), i];
        }
        storeMap.set(nums[i], i);
    }
    return [];
};

Conclusion

I want to emphasize again when to use hash methods: whenever you need to check if an element has appeared before, or if an element is in a set, you should immediately think of using hash methods.

To decide use wether array, set, or map, consider the constrains of them:

Array - The size of an array is limited, and if there are few elements but the hash values are too large, it will lead to a waste of memory space.

Set - A set is a collection that can only contain keys. In problems like “two-sum”, where we not only need to check if difference value (x) exists but also need to record the index of this number (y) because we need to return the indices of x and y, a set is also not suitable.

Map - A map is a collection that has a key-value structure. Only consider use map if it requires to store 2 layer data that requires you to use key-value structure. Otherwise use the above two instead.