Dans cet article, je vais résoudre le problème de la somme de trois nombres dont la valeur est la plus proche possible d’une cible donnée.
L’objectif est de proposer deux méthodes de résolution. La première repose sur une approche naïve et peu efficace, tandis que la seconde sera optimisée.
Enfin, une comparaison entre les deux méthodes permettra d’analyser leurs performances respectives.
Selon le site LeetCode, la difficulté de ce problème est moyenne.
Given an integer array nums of length n and an integer target, find three integers at distinct indices in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Contraintes :
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104Dans cette méthode, nous explorons une approche par force brute. Cette approche est directe et consiste à parcourir l’ensemble des combinaisons possibles de trois nombres afin de minimiser la distance entre leur somme et la valeur cible.
Il est important de noter que l’addition est une opération commutative. Cela permet d’ignorer les éléments situés avant l’indice courant. Ainsi, chaque boucle imbriquée commence à l’indice suivant celui de la boucle englobante.
Dans le cas contraire, certaines combinaisons seraient évaluées plusieurs fois, ce qui augmenterait inutilement le temps d’exécution.
class Solution
{
public:
int threeSumClosest(vector<int>& nums, int target) {
// brute force
if (nums.size() < 3) return 0;
int sum = nums[0] + nums[1] + nums[2], temp = 0;
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
for (int k = j + 1; k < nums.size(); k++)
{
temp = nums[i] + nums[j] + nums[k];
if (abs(temp - target) < abs(sum - target))
sum = temp;
}
}
}
return sum;
}
};
Dans cette section, une approche optimisée sera présentée. Elle repose généralement sur le tri du tableau suivi de l’utilisation de deux pointeurs afin de réduire la complexité temporelle.
La solution par force brute présente une complexité temporelle élevée, de l’ordre de O(n³), ce qui la rend peu adaptée aux grandes tailles d’entrée.
En revanche, la solution optimisée permet de réduire significativement le temps d’exécution, tout en conservant une consommation mémoire raisonnable.
Ce problème met en évidence l’importance du choix de l’algorithme dans la résolution d’un problème. Une approche naïve peut être simple à implémenter, mais elle devient rapidement inefficace lorsque la taille des données augmente.
L’utilisation de techniques d’optimisation permet d’améliorer considérablement les performances, tant en termes de temps d’exécution que de scalabilité.