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]

Recommended Posts

Algorithm Gymnastics 20 Pair with Target Sum
Algorithm gymnastics 12
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
[Python3] Dijkstra's algorithm with 14 lines
group_by with sqlalchemy and sum