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]

Recommended Posts

Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 12
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
[Python3] Méthode Dikstra avec 14 lignes
Group_by avec sqlalchemy et sum