Given an array of integers and an integer target, return indices of the two numbers such that they add up to target.
Example:
Given int[] a = { 1, 2, 5, 7 } and Target = 8
Answer = {0,3}
Explanation:
In the given array we know that the first element a[0] and the last element a[3] add up to target = 8.
Solution:
The optimal solution that will run O(N) time would be to use the dictionary data structure.
First, we will run through the array elements and throw target - a(i) in to the dictionary because we want to find any element in the array if it is target - a(i), where a(i) is any element of the array. This makes sense if we solve for b in the equation:
a(i) + b = target. [find any two pairs a(i) , b so that a(i) + b = target]. Then b = target - a(i)
Then we are going to iterate through the array elements second time and find if any one of them are present in the dictionary and if it does then that is what we want.
public int[] solution(int[] A, int target){
int [] a = new int[2];
Dictionary<int, int> dict = new Dictionary<int, int>();
int j = 0 ;
for(int i=0; i < A.Length; i++){
if(!dict.ContainsKey(i))
dict.Add(i, target - A[i]);
}
for (int i = 0; i < A.Length; i++){
if (dict.ContainsValue(A[i])){
a[j] = i; j++;
}
if (j == 2) break;
}
return a;
}