 # Two Sum

Problem Source LeetCode
Companies: Google, Amazon, Apple, Microsoft, Adobe, Facebook, Oracle, Nvidia, SAP, Paypal, Walmart Labs, Samsung

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

Given nums = [3, 6, 12, 4], target = 15,

Because nums + nums = 3 + 12 = 15,
return [0, 2].

### Solution:

This problem can be solved using Brute Force. In this, we have two go through each element `x` and then check if there exist an element which is equal to `target - x`. The time complexity of this implementation will be O(n2).

Another approach to solve this problem is use of Hash Tables. In this implementation mapping of the value of element with its index is done. We will iterate through the array and keep on inserting every element together-with, we will check if there exist a complement of the current element. If exist, we will return there indexes and break the loop, otherwise move forward and insert elements into the hash table.

#### Java Implementation

```public static class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
} else {
map.put(nums[i], i);
}
}
return new int[]{-1, -1};
}
}```

#### C++ Implementation

```#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> result;
for(int i = 0; i < nums.size(); i++){
// not found the second one
if (m.find(nums[i]) == m.end() ) {
// store the first one poisition into the second one's key
m[target - nums[i]] = i;
} else {
// found the second one
result.push_back(m[nums[i]]);
result.push_back(i);
break;
}
}
return result;
}
};```

#### Python Implementation

```class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
two = {}
for i, num in enumerate(nums):
if target - num in two:
return (two[target - num], i)
two[num] = i```

### Complexity Analysis:

• Time Complexity: O(n).
• Space complexity: O(n)
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.