[PYTHON] Algorithm Gymnastics 20 Pair with Target Sum

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.

example

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:

1. If the sum of the two numbers pointed to by the two pointers is greater than the sum of the targets, this means that you need a pair with a smaller sum. Therefore, you can decrement the end pointer.
2. If the sum of the two numbers pointed to by the two pointers is less than the sum of the targets, it means that a larger sum pair is needed. Therefore, you can increment the start pointer.

Implementation

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]