Given two list of integers and a target number k, we want to find pairs (one number from each array) that add up to target number k.
Example:
Let A = { 1,1, 2, 3,5,6 } and B= { 2, 3, 4, 5,8 }; and Target=10
We need to return the pairs [2,8] , [5,5], [6,4] as these pairs are selectively picked from each array since each pair add up to target sum 10.
Solution:
We can solve this problem by first iterating on the first array and calculate k-a(i) and save it in a dictionary where k-a(i) is the key and a(i) is the value.
Then we can iterate through the second array and see if each element is in the dictionary and if it does we found our first pair and we save it in a hashset.
public HashSet<KeyValuePair<int, int>> FindPairsAddupToTarget(int [] A, int [] B, int k) {
Dictionary<int, int> dict = new Dictionary<int, int>();
HashSet<KeyValuePair<int, int>> pairs = new HashSet<KeyValuePair<int, int>>();
for(int i=0; i < A.Length; i++) {
int diff = k - A[i];
if(!dict.ContainsKey(diff))
dict.Add(diff,A[i]);
}
foreach(int item in B) {
if (dict.ContainsKey(item))
pairs.Add(new KeyValuePair<int, int>(item, dict[item]));
}
return pairs;
}