Pair with Target Sum
Specify an array of sorted numbers and a sum of objects to find a pair of arrays whose sum is equal to the specified object. Create a function that returns an index (that is, a pair) of two numbers. If the pair does not exist, it returns index -1.
Input: [1, 2, 3, 4, 6], target=6 Output: [1, 3]
Input: [2, 5, 9, 11], target=11 Output: [0, 2]
Solution A double pointer approach is available. Start with a pointer to the beginning and a pointer to the end of the array. At every step, check if the numbers pointed to by the two pointers add up to the total target. If so, you have found the pair. Otherwise, do one of the following two things:
def pair_with_targetsum(arr, target_sum):
left_pointer = 0
right_pointer = len(arr) - 1
while left_pointer < right_pointer:
sum = arr[left_pointer] + arr[right_pointer]
if sum == target_sum:
return [left_pointer, right_pointer]
if sum > target_sum:
right_pointer -= 1
else:
left_pointer += 1
return [-1, -1]
Recommended Posts