Récemment, hashedin a posé le problème de la somme des triplets où trois nombres sont censés s'additionner à une somme cible. Ils ont dit de le faire en O (n).
J'ai essayé de le faire en O (n ^ 2). Tout d'abord, j'ai trié le tableau, puis pour rechercher la combinaison, j'ai dû appliquer la technique de la fenêtre coulissante à tous les éléments du tableau. Je ne parviens pas à le réduire à O (n).
def threeNumberSum(array, targetSum):
array.sort()
l = len(array)
trip = list()
for i in range(l-2):
left = i+1
right = len(array)-1
while left<right:
currentSum = array[i] + array[left] + array[right]
if currentSum == targetSum:
trip.append([array[i], array[left], array[right]])
left += 1
right -= 1
elif currentSum < targetSum:
left += 1
else:
right -= 1
return trip
Ce code renvoie en fait toutes les combinaisons de sommes possibles. Mais selon l'entreprise, un seul triplet est nécessaire. Tous les triplés possibles ne sont pas nécessaires
4 Réponses :
La meilleure approche possible pour trouver un seul triplet est en O (n ^ 2) uniquement, il peut y avoir un malentendu entre vous et l'intervieweur. Il est impossible de le faire en O (n). Bon codage!
Il s'agit d'une solution basée sur le hachage qui a la complexité O (n) Programme Python3 pour trouver un triplet en utilisant Hashing, retourne true s'il y a un triplet avec une somme égale à 'sum' présent dans A []. Affiche également le triplet
def find3Numbers(A, arr_size, sum):
for i in range(0, arr_size-1):
# Find pair in subarray A[i + 1..n-1]
# with sum equal to sum - A[i]
s = set()
curr_sum = sum - A[i]
for j in range(i + 1, arr_size):
if (curr_sum - A[j]) in s:
print("Triplet is", A[i],
", ", A[j], ", ", curr_sum-A[j])
return True
s.add(A[j])
return False
Comment cette solution fonctionnera en O (n)? Je pense que ce code a une complexité temporelle de O (n ^ 2).
Il n'est pas possible de le faire en temps O (n) complexité.
Le code python mentionné comme ANSWER lui-même a une boucle for imbriquée, donc dans tous les cas, la complexité du pire des cas serait O (n ^ 2). Cas de test: 3 4 5 2 2 19 Somme requise = 23. Ce cas de test ne peut pas être résolu en O (n). Un peu de responsabilité devrait être là si quelqu'un répond sur stackoverflow.
Merci à tous d'avoir essayé de vous aider. J'ai trouvé une première solution pour le faire en O (n). Je ne sais pas encore si c'est correct, mais il fonctionne sur tous les cas de test Voici un lien Github pour télécharger le fichier python github.com/TripletInArrayWithTargetSum
def trip(arr, target):
d = dict()
n = len(arr)
for i in arr:
d[i] = 1
i = 0
j = n - 1
while i<j:
s = arr[i] + arr[j] # Calculate the sum of the elements at i and j position
diff = target - s # Calculate the difference needed to complete the table
if arr[i] != diff and arr[j] != diff and diff in d: # Check if the difference exists in the hashtable and as we cannot reuse elements
return [arr[i], arr[j], diff] # diff should not be equal to elements at i or j and then return the triplet if exists
else:
if s > target: # If difference dosent exists then we adjust pointers
j -= 1
elif s == target:
if arr[i+1] + arr[j] < target:
i+=1
else:
j-=1
else:
i += 1
return [None]
Téléchargez le fichier complet avec les cas de test sur Github