@paul_416, Unfortunately @mattlee42011-hotmail-com's solution wont work. Imagine the given input is [2,4] and [3,8] and target is 10. His solution would return 1 since the first pair sum would be 5 and the next would be 10 but it would be incorrect since the correct order is [5,7,10,12] and the answer is index 2. Your solution, on the other hand, is very clever. Thanks for sharing it. Below is a python version inspired by it.
The reason I keep nums1 to be the smaller array is that I want my complexity to be O(nlogm) where m is the length of the larger array. Hence, I am speeding it up by taking the logarithm of the larger array.import bisect def pairwisesum(nums1, nums2, target): if not nums1 or not nums2: return -1 nums1.sort() nums2.sort() n, m = len(nums1), len(nums2) if n > m: nums1, nums2 = nums2, nums1 n, m = m, n count = 0 for n in nums1: i = bisect.insert_left(nums2, target - n) if i >= 0 and i < m and nums2[i] == target - n: count += i return i count += i return -1