Two Sum

Problem Statement

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.

Link to GitHub : code

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

• We need a HashMap to store the previous key value and index of the array
• If a in unknown in a+b=c then we can use  c-b =a  to find a. We are doing this using by adding the key value as map.put(target-arr[i],i). We are also storing the index value in HashMap
• First iteration would always fail as HashMap would be empty
• If the current array element contains the key value stored in HashMap, we know that we have found the Two sum array index.

public static int [] get(int [] arr,int target)
 {
  //Array to store the indices
  int [] result= new int[2];
  
  Map<Integer,Integer> map= new HashMap<Integer,Integer>();
  for(int i=0;i<=arr.length;i++){
   //Check if the key exists in HasMap
   if(map.containsKey(arr[i])){
    result[0]=map.get(arr[i]);
    result[1]=i;
    return result;
   }
   map.put(target-arr[i],i);
  }
  return result;
    
 }

Iteration