**Problem Statement:** Given an array of integers nums[] and an integer target, return *indices of the two numbers such that their sum is equal to the target*.

**Note**: Assume that there is ** exactly one solution**, and you are not allowed to use the

*same*element twice. Example: If target is equal to 6 and num[1] = 3, then nums[1] + nums[1] = target is not a solution.

**Example** 1:

Input:nums = [2,7,11,15], target = 9Output: [0,1]Explanation: Because nums[0] + nums[1] == 9, which is the required target, we return indexes [0,1]. (0-based indexing)

**Example 2**:

Input Format:nums = [3,2,4,6], target = 6Output: [1,2]Explanation: Because nums[1] + nums[2] == 6, which is the required target, we return indexes [1,2].

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: Naive Approach (Brute Force)**

**Intuition**: For each element, we try to find an element such that the sum of both elements is equal to the given target.

**Approach**: We traverse through the array, and for each element **x**, we try to find another element amongst the remaining elements, such that the sum of both the elements equals the target.

- Let, first Element is
**x**. The required second element will be,**target – x** - If we find both the elements, we break the loop and return the indices.

**Dry Run**: Given array, nums = [2,1,3,4], target = 4

Using the naive approach, we first select one element and then find the second element.

- For index 0, x= 2
- Then, we iterate through index 1 to 3 to check if
**target – x,**i.e. 4 – 2 = 2 exists. 2 does not exists from index 1 to 3, we move to next index.

- Then, we iterate through index 1 to 3 to check if
- For index 1, x=1
- Then, we iterate through index 2 to 3 to find if
**target – x,**i.e. 4 – 1 = 3 exists. 3 exists at index 2, so we store the indices 1 and 2, break the loop, and return the indices.

- Then, we iterate through index 2 to 3 to find if

**Code**:

## C++ Code

```
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[i] + nums[j] == target) {
res.emplace_back(i);
res.emplace_back(j);
break;
}
}
if (res.size() == 2)
break;
}
return res;
}
```

**Time Complexity: **O(N^{2})

**Space Complexity: **O(1)

**Solution 2: Two-Pointer Approach**

**Intuition**: Think about, what if the array is sorted? If the array is sorted, is it possible to reach a sum by traversing the array from both sides simultaneously?

We **sort the array**, use two variables, each will start from one end of the array, and traverse in both directions till we get the required sum.

**Approach**: First we create duplicate array and sort that array. Then we traverse through the array, and for each element **x**, we try to find another element amongst the remaining elements, such that the sum of both the elements equals the target.

- Let, first Element is
**x**. - The required second element will be,
**target – x** - If we find both the elements, we break the loop and return the indices.

**Dry Run**: Given array, nums = [2,1,3,4], target = 4

- First we sort the array. So nums after sorting is [1,2,3,4]
- We take two pointers,
**i**and**j**. i points to index 0 and j points to index 3. - Now we check if nums[i] + nums[j] == target. In this case, they don’t sum up, and nums[i] + nums[j] > target, so we will reduce j by 1.
- Now, i = 0, j=2
- Here, nums[i] + nums[j] == 1 + 3 == 4, which is the required target, so we store both the elements and break the loop.
- Now, we run another loop to find the indices of the elements in the actual array, i.e [2,1,3,4]
- Then, return the actual indices, [1,2].

**Code**:

## C++ Code

```
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res,store;
store = nums;
sort(store.begin(), store.end());
int left=0,right=nums.size()-1;
int n1,n2;
while(left<right){
if(store[left]+store[right]==target){
n1 = store[left];
n2 = store[right];
break;
}
else if(store[left]+store[right]>target)
right--;
else
left++;
}
for(int i=0;i<nums.size();++i){
if(nums[i]==n1)
res.emplace_back(i);
else if(nums[i]==n2)
res.emplace_back(i);
}
return res;
}
```

**Time Complexity: **O(NlogN)

**Space Complexity: **O(N)

**Solution 3: Hashing (Most efficient)**

**Approach**: We can solve this problem efficiently by using **hashing**. We’ll use a** hash-map** to see if there exists a value **target – x** for each value **x**. If **target – x **is found in the map, can return current element **x’s** index and **(target-x)’s** index

This can be done in constant time.

**Dry Run**: Given array, nums = [2,3,1,4], target = 4

- For index 0, x = 2 and currently map is empty.
- We try to find if
**target – x = 4 – 2 = 2**is present in the map or not. - For now, 2 does not exists in the map.
- And we store the index of element 2. i.e., mp[2] = 0,

- We try to find if
- For index 1,
**x**= 3- We try to find if
**target – x = 4 – 3 = 1**is present in the map or not. - For now, 1 does not exists in the map.
- And we store the index of element 3. i.e., mp[3] = 1,

- We try to find if
- For index 2, x = 1
- We try to find if
**target – i = 4 – 1 = 3**is present in the map or not. 3 exits in the map, so we store index 2 and value stored for key 3 in the map, and break the loop. And return [1,2].

- We try to find if

**Code**:

## C++ Code

```
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); ++i) {
if (mp.find(target - nums[i]) != mp.end()) {
res.emplace_back(i);
res.emplace_back(mp[target - nums[i]]);
return res;
}
mp[nums[i]] = i;
}
return res;
}
```

**Time Complexity: O(N)**

**Space Complexity: O(N)**

Special thanks to Pranendu Bikash Pradhan for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article.