In this article, we will be discussing the two sum problem and how it can be solved using the programming languages C++, Java, and Python

**Problem Statement**

## two sum java

This is another article in the series

**leetcode problem solutions**and this article is a

**solution to leetcode 1 two sum problem**.

There are many ways to solve this problem, but we will be focusing on three methods: a brute force approach, a sorting approach, and a hashtable approach. We will be discussing the time complexity and space complexity of each method as well as any trade-offs that need to be made.

Once you have a good understanding of** two sum problem,** it should help you s**olve advanced level problem**s like **three sum** which in some ways a **continuation of the two sum problem**.

Consider you are given an **array of integers** and a **target sum**, return indices of** two numbers i**n the array such that they add up to the given target. You may assume that each input would have exactly one solution. Also, you cannot use the same element twice. You are allowed to return the answer in any order.

Example

**Example 1:**

Input: nums = [7,2,13,11], target = 9

Output: [0,1]

Example 2:

Input: nums = [7,3,5], target = 8

Output: [1,2]

**Solution:**

First, let us attempt to comprehend the issue statement. We are provided an array of integer items as well as a goal total. Our task is to build an algorithm that returns the indices of two entries in this array so that when we combine these two elements, the total should equal the goal amount.

In example 1, the supplied array is [7,2,13,11], and the specified goal total is 9. Looking at the supplied array, the pair that adds to the goal total 9 is (7,2), i.e. 7+2 = 9. As a consequence, our method should return(0,1) as the result because they are the indices of items 7 and 2 in the supplied array, respectively.

** Use of Force**

A simple approach to this problem is to look for every possible pair in the supplied array.

We must do the following steps for a given input array nums:

Run two loops to test each combination in the supplied array.

To acquire all potential pairs, fix the outer loop at a given index and shift the inner loop. The outer loop extends from i=0 to i=n-2, whereas the inner loop extends from j=i+1 to j=n-1.

Check if the integers represented by the outside and inner loop indexes add up to the goal total in each iteration of the inner loop.

If nums[outerLoopIndex] + nums[innerLoopIndex] equals target, the outcome is outerLoopIndex, innerLoopIndex. Otherwise, keep iterating to ensure

## 2) Hashmap is the second solution.

This issue can be solved in linear time. The concept is to utilise a hashmap to record the indices of previously visited items. The “key” of a hashmap is the number in the specified input array (You add this to the hashmap as you visit each element). The index of the number in the array represented by the hashmap key is the hashmap “value.”

This method performs the following stages for a given input array:

- Make a hashmap with integer datatypes as keys and values.
- Iterate through each element in the specified array, beginning with the first.
- Check the hashmap for the presence of the needed number (required number = goal sum – current number) in each iteration.
- If present, return the result necessary number index, current number index.
- Otherwise, add the current iteration number as a key to the hashmap and its index as a value. Repeat until you discover the answer.

**Simulation**

Consider the following input array with goal = 24.

Let currIdx be the variable representing the currently processed element, and idxMap be our index map. Orange cells represent the array member that is presently being processed.

As indicated in the first figure below, currIdx = 0 and idxMap is empty at the start. Then we check to see if the needed number = target – current number exists in the idxMap.

Because the required number = 24 – 7 = 17 is not present in our hashmap, we add 7 as an idxMap key and 0 as an idxMap value.

**JAVA**

There are many ways to solve the two sum problem in Java. One way is to use a brute force approach, which is to try every possible combination of numbers until you find a pair that sums to the target number. Another way is to use a hash table, which can be used to store all the possible sums and their corresponding indices.

If you’re looking for a more efficient solution, you can use a sorting algorithm such as quicksort or heapsort. Once the array is sorted, you can iterate through it and find the pair that sums to the target number. This solution has a time complexity of O(n log n).

If you have any questions about solving two sum in Java, feel free to leave a comment below!

```
Map hm = new HashMap();
for(int i=0;i {
hm.put(nums[i],i);
}
for(int i=0;i {
int k =nums[i];
if(k == target && hm.containsKey(0) )
{
arr[0]= i;
arr[1]=hm.get(0);
break;
}
else if(hm.containsKey(target-k) )
{
if(hm.get(target-k)>i)
{ arr[0]= i;
arr[1]=hm.get(target-k);
break;}
}
}
return arr;
}
```

**CPP:**

```
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> visited;
int len = nums.size();
for (int i = 0; i < len; ++i) {
int n = nums[i];
int complement = target - n;
if (visited.count(complement)) {
return {visited[complement], i};
}
visited[n] = i; // assume that each input would have exactly one solution
}
return {};
}
};
```

**Python :**

Python is a programming language with many features and libraries that can be used to solve a variety of problems. One such problem is the Two Sum problem, which can be solved using a variety of methods.

**Time Complexity brute force search.**

Finally, another approach that can be used to solve the Two Sum problem is to use a** brute force search.** This approach works by iterating through all pairs of numbers in the array and checking if their sum equals the target sum. The time complexity of this approach is O(n^2), which makes it less efficient than other methods.

**Time Complexity hash table**

The most common method for solving the Two Sum problem is to use a** hash table**. This approach works by iterating through the array of numbers and inserting each number into a hash table. If the number being inserted is already in the hash table, then it is considered a sum. The time complexity of this approach is O(n), where n is the size of the array.

**Two pointers**

```
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n=nums.size();
int a[n];
//3 2 4
//sorted arr 2 3 4 //l=0,r=2 check value at l and r and match with the copy of given array element
for(int i=0;i<nums.size();i++){
a[i]=nums[i];
}
vector<int>v;
sort(nums.begin(),nums.end());
int l=0,r=nums.size()-1;
while(l<r){
if(nums[l]+nums[r]==target){
break;
}
else if(nums[l]+nums[r]>target){
r--;
}
else{
l++;
}
}
for(int i=0;i<n;i++){
if(nums[l]==a[i]){
v.push_back(i);
}
else if(nums[r]==a[i]){
v.push_back(i);
}
}
return v;
}
};
```

Another approach that can be used to solve the Two Sum problem,firtly make the copy of array and then sort the array and then use **two pointers, **one from each end of the array, to find the sum. This approach has a time complexity of O(n log n) due to the need to sort the array.

### Algorithm Working

The program starts by creating a copy of the `nums`

array called `a`

. Then, it sorts the `nums`

array in ascending order using the `sort()`

function from the STL library.

Next, the program initializes two pointers `l`

and `r`

to the beginning and end of the sorted array, respectively. The program enters a while loop that continues until `l`

is greater than or equal to `r`

. At each iteration, the program checks whether the sum of the integers at `l`

and `r`

is equal to the `target`

. If it is, the program exits the loop. If the sum is greater than the `target`

, the program decrements `r`

. If the sum is less than the `target`

, the program increments `l`

.

After the while loop, the program loops through the o**riginal nums array** and checks whether each element is equal to either

`nums[l]`

or `nums[r]`

. If an element is equal to either `nums[l]`

or `nums[r]`

, its index is added to the vector `v`

.Finally, the program returns the vector `v`

containing the indices of the two numbers that add up to the `target`

.

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

Python

```
def twoSum(nums, target):
n = len(nums)
a = nums.copy()
nums.sort()
l = 0
r = n - 1
while l < r:
sum = nums[l] + nums[r]
if sum == target:
break
elif sum > target:
r -= 1
else:
l += 1
v = []
for i in range(n):
if nums[l] == a[i]:
v.append(i)
elif nums[r] == a[i]:
v.append(i)
return v
```

JavaScript Solution :

```
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const n = nums.length;
const a = [...nums];
nums.sort((a, b) => a - b);
let l = 0;
let r = n - 1;
while (l < r) {
const sum = nums[l] + nums[r];
if (sum === target) {
break;
} else if (sum > target) {
r--;
} else {
l++;
}
}
const v = [];
for (let i = 0; i < n; i++) {
if (nums[l] === a[i]) {
v.push(i);
} else if (nums[r] === a[i]) {
v.push(i);
}
}
return v;
};
```

Dart Solution :

```
List<int> twoSum(List<int> nums, int target) {
final n = nums.length;
final a = [...nums];
nums.sort();
var l = 0;
var r = n - 1;
while (l < r) {
final sum = nums[l] + nums[r];
if (sum == target) {
break;
} else if (sum > target) {
r--;
} else {
l++;
}
}
final v = [];
for (var i = 0; i < n; i++) {
if (nums[l] == a[i]) {
v.add(i);
} else if (nums[r] == a[i]) {
v.add(i);
}
}
return v;
}
```

In this article, you have learned how to solve the **Two Sum problem using C++, Java, and Python.** You have also seen how the ThreeSum problem can be solved as a special case of the TwoSum problem. I hope you have found this article helpful and that you now have a better understanding of how to solve these types of problems.

bro you solved it by class method and python code for this problem is simpler but i cant understand why we use class and all so please refer me article so that i can understand is use.

Thankyou.

The Class Solution is Only For the Leetcode .Which call the function inside the class

the CPP code is not working and you didn’t explain the method using hashmaps(the method used in the code)

Bro, python code is correct —

Itís nearly impossible to find well-informed people for this subject, however, you seem like you know what youíre talking about! Thanks

Please write the dart code for this problem

Wһat’s up to every one, it’s truly a good for me to рay a

quick visit this site, it contains preci᧐us Information.

what if Input: nums = [0,9,7,2,13,11], target = 9

what will be the output ?

the quetion has not include this condition but both [0,1] and [2,3] are correct answer.

Your python hash table solution is not n… it’s n^2.

Checking if an element is in a dict is amortized worst case O(n). You perform this check n times. Therefore n^2…

https://wiki.python.org/moin/TimeComplexity

Mine as well just brute force it

0,1

I do not even understand how I ended up here, but I assumed this publish used to be great

You’re so awesome! I don’t believe I have read a single thing like that before. So great to find someone with some original thoughts on this topic. Really.. thank you for starting this up. This website is something that is needed on the internet, someone with a little originality!

I am truly thankful to the owner of this web site who has shared this fantastic piece of writing at at this place.