Gymnastique d'algorithme 20 paires avec somme cible

Pair with Target Sum

Spécifiez un tableau trié de nombres et une somme d'objets pour trouver une paire de tableaux dont la somme est égale à l'objet spécifié. Créez une fonction qui renvoie un index (c'est-à-dire une paire) de deux nombres. Renvoie l'index -1 si la paire n'existe pas.

exemple

Input: [1, 2, 3, 4, 6], target=6 Output: [1, 3]

Input: [2, 5, 9, 11], target=11 Output: [0, 2]

Solution Une approche à double pointeur est disponible. Commencez par un pointeur vers le début du tableau et un pointeur vers la fin. À chaque étape, vérifiez si les nombres pointés par les deux pointeurs correspondent à la cible totale. Si tel est le cas, vous en avez trouvé une paire. Sinon, effectuez l'une des deux opérations suivantes:

1. Si la somme des deux nombres pointés par les deux pointeurs est supérieure à la somme des cibles, cela signifie que vous avez besoin d'une paire avec une somme plus petite. Par conséquent, vous pouvez décrémenter le pointeur de fin.
2. Si la somme des deux nombres pointés par les deux pointeurs est inférieure à la somme des cibles, cela signifie qu'une plus grande paire de somme est nécessaire. Par conséquent, vous pouvez incrémenter le pointeur de départ.

la mise en oeuvre

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]