Given 2 unsorted arrays and a sum, give two numbers that, when added, equal the sum

Question

In these arrays, the numbers can be either positive or negative. Only one number from each array may be used.

I received this question as an algorithms question on a phone interview and it stumped me. The interviewer seemed to believe there was an O(n) solution.

Edit: My question is different than the "possible duplicates" because this question involves 2 arrays, rather than one.

Possible duplicate of [Find a pair of elements from an array whose sum equals a given number](http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number) — shole, Apr 20 '17 at 05:07

score 6 · Accepted Answer · answered Apr 20 '17 at 02:07

6

For unsorted arrays - fill hash table with the first array values and walk through the second one, checking if Sum-B[i] exists in the table

answered Apr 20 '17 at 02:07

MBo

72,080
5
47
77

Thanks! I guess I need more practice with questions that expect you to implement a hash table. – C. Parks Apr 20 '17 at 12:41

Given 2 unsorted arrays and a sum, give two numbers that, when added, equal the sum

1 Answers1