# 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:

```Given nums = [2, 7, 11, 15], target = 9,
Because nums + nums = 2 + 7 = 9, return [0, 1].```

## Explanation

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

Simply, we can use a nested loop to solve. We can use a variable i to visit each element and use another variable j to check if there is another element in array add variable i value equal to target. 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 can introduce a HashMap to reduce time complexity. The HashMap stores visited element values and indexes. Every time we visit an element, we store the element value and index into the HashMap, and we check if the 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).

## Java Solution

``````public class Solution {

public int[] twoSum(int[] nums, int target) {
int[] result = new int;

Map<Integer, Integer> visited = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (visited.containsKey(target - nums[i])) {
result = visited.get(target - nums[i]);
result = i;
return result;
}
visited.put(nums[i], i);
}

return result;
}
}``````

## Python Solution

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
result = []
visited = {}

for i, num in enumerate(nums):
complement = target - num

if complement not in visited:
visited[num] = i
else:
result.append(i)
result.append(visited[complement])

return result``````

## 3 Thoughts to “LeetCode 1. Two Sum”

1. Stephen Boesch says:

This is *time* efficient but not *space* efficient. If we are not permitted to use extra space then sorting in place and using pointers is an O(nlogn) solution.

2. aarjay singh says:

Hey There,
I really like your video tutorial. Would you be interested in teaching on 1:1 basis.