LeetCode 1. Two Sum

Description

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Explanation

The question is about finding two elements in an array that they add up to the given target.

Simply, we can use a nested loop to solve the problem. We have an i variable to visit each element and we have another variable j to check if there is another value that equals to target – nums[i. The idea is easy. However, the solution is not efficient. The time complexity would be O(N²).

There is a better way to solve the problem. We introduce a HashMap. We stored visited elements values and indexes into the HashMap. Every time we visit an element, we store the element value and index into the HashMap, and we check if current element’s complement already exists in the HashMap. If the complement exists, we find a solution. The solution is efficient. Time Complexity is O(N).