Two Sum problem in Java

Hi coders! In this tutorial, we are going to solve a problem that is related to a very common data structure known as the Array. To solve the two sum problem in Java, we will use HashMap.

The problem is like, we have given an array of integers and we have to return the indices of the two numbers so that they add up to a specific target.

There are various methods to solve this problem, one of them is a naive approach to use two loops and check pair for each number. This solution is going to give O(n^2) time complexity so we switch to a better approach that can be done by using a HashMap.

Note: Assuming that give array has exactly one solution and also we cannot use the same element twice.

 HashMap  method to solve two sum problem in Java

• First of all, we are going to take a HashMap of <Integer, Integer> i.e. of <key, value> pair.
• Then in the loop, we will check if the pair of the current accessed element is present in the HashMap or not.
• If found in the HashMap, we will print the indices else we will put the element in the HashMap.

Example:
Given nums = [2, 7, 11, 15, 19],target = 13
since nums[0] + nums[2] = 13 
return [0, 1].

Code Implementation in Java

import java.util.*;
public class Example {
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15, 19};
int target = 13;
int[] arr = twoSum(nums, target);
for(int i = 0; i < 2; i++) {
System.out.print("["+arr[i]+ " ]");
}
}
private static int[] twoSum(int[] nums, int target) {
int[] arr = new int[2];
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
 for(int j = 0; j < nums.length; j++) {
    Integer value = map.get(target - nums[j]);
  if(value == null) { /* no match found */
    map.put(nums[j], j);
   }
else {     /* pair found, updating index */
    arr[0] = value;
    arr[1] = j;
    break; //  loop exit
   }
}
   return arr;
}
}
// The code is provided by Anubhav Srivastava

Output: 
[0 2]

Hence the code has the time complexity of O(n) and the space complexity is also  O(n).

I hope you like the solution.

Also read:

• Lucky Seven Problem in Java
• Tower of Hanoi Problem using recursion in Java

One response to “Two Sum problem in Java”

1. Sebastian Peter says:

   September 27, 2020 at 9:31 am

   You need to put import java.util.HashMap; to execute it.

   Reply