You have two integer arrays,
b, and an integer target value
v. Determine whether there is a pair of numbers, where one number is taken from
a and the other from
b, that can be added together to get a sum of
true if such a pair exists, otherwise return
a = [1, 2, 3],
b = [10, 20, 30, 40], and
v = 42, the output should be
sumOfTwo(a, b, v) = true.
- [time limit] 4000ms (py)
- [input] array.integer aAn array of integers.
1 ≤ a.length ≤ 105,
-109 ≤ a[i] ≤ 109.
- [input] array.integer bAn array of integers.
1 ≤ b.length ≤ 105,
-109 ≤ b[i] ≤ 109.
- [input] integer vConstraints:
-109 ≤ v ≤ 109.
- [output] boolean
trueif there are two elements from
bwhich add up to
We can do this in len(a)*len(b) operations iterating over every single x,y combination but it would not run in short time. Therefore, we need a smarter solution. If we had two sorted arrays, then we would be sure that whenever we go to the next element in the array, the sum would increase. Similarly, previous element would make the sum decrease.
Following that, if we start from the beginning of one array and end of the other. We can travel within the arrays and check the sum everytime.
For example, if we have [1,2,3,5] and [10,20,30,40] and we are looking for 33, we can do the following:
start from the beginning of first array and at the end of second
sum = 41
it is greater than our sum, so move the iterator in the second array to the left ro decrease the sum.
1+30 = 31
It is smaller, then move the iterator in the first array forward so that the sum increases
2+30 = 32
If we were looking for 34, we would go to the next element, 35 would be bigger than the number we are looking for. That means we have no way of making the sum with these numbers because the smaller x’s are all depleted and bigger numbers will always result in bigger sums than we are looking for.
Feel free to shoot any questions.