3Sum Closest

Table de matières

• Introduction
• Enoncé du ploblème
• Première solution
• Deuxième solution
• Comparaison
• Conclusion

Introduction

Dans cette article, je vais essayer de résoudre le problème de la somme de trois nombres proche d'un ciblre donnée. Le but de resoudre le problème de deux méthodes. La première doit être non efficace et la deuxième doit être efficace.
Aprés, il faut comparer les deux méthodes. La difficulté de ce problème selon le site Leetcode est moyenne.

Enoncé du ploblème

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.

Première solution

Dans cette méthode, on va explorer la force brute. Cette approche est directe. Elle se base sur l'expérimentation de tout l'espace de possibilité en minimisant la distance entre la somme de trois nombres et la valeur cible.
Il faut bien noter que la somme est commutative. Donc, ça nous permet d'ignorer les nombres à gauche. Pour cette raison, la boucle for imbriqué commencent par le nombre qui suit la boucle englobante. Dans le cas contraire, on aura un temps d'exécution presque doublé.

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 =                     
                    }
                }
            }
            return sum;
        }
};
        

Deuxième solution

Comparaison

Conclusion