Discussion :

[serpentcorail]

Bonjour à la communauté

vu sur letscode :

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.


pour [-1,0,1,2,-1,-4]

on devrais obtenir ça [[-1,-1,2],[-1,0,1]]


Je ne comprend pas cette condition : such that i != j, i != k, and j != k

cordialement

[dourouc05]

Ca veut dire que tu dois prendre des éléments distincts dans ta liste (sans compter la valeur, mais uniquement la position dans la liste).

[serpentcorail]

Ca veut dire que tu dois prendre des éléments distincts dans ta liste (sans compter la valeur, mais uniquement la position dans la liste).

merci de ta réponse

je vais réfléchir à ça demain je tombe de sommeil

[WhiteCrow]

C'est un sujet sympatoche …
Ma première idée plutôt brute me donne une solution en O(n² logn) temps et O(1) espace, puis ensuite j'en ai une autre en O(n²) temps et O(n) espace, mais on peut se débrouiller en juste O(n²) temps et O(1) espace je pense …
à creuser …
fais nous part de tes avancées 👍

[serpentcorail]

qqu pourrait me dire pk par exemple [-1,-1,0] n'est pas accepté ?

[WhiteCrow]

parce que -1 + -1 + 0 = -2 ≠ 0 …

[serpentcorail]

parce que -1 + -1 + 0 = -2 ≠ 0 …

je me suis trompé

voila mon output pour l'instant :

[[-1,0,1],[-1,1,0],[-1,2,-1],[-1,-1,2],[0,-1,1],[0,1,-1],[0,1,-1],[0,-1,1],[1,-1,0],[1,0,-1],[1,0,-1],[1,-1,0],[2,-1,-1],[2,-1,-1],[-1,-1,2],[-1,0,1],[-1,1,0],[-1,2,-1]]


ils font tous 0 mais seulement deux sont bon , pk ? s'il vous plais

[WhiteCrow]

parce que tu as des doublons
[-1,0,1] c'est la même chose que [-1,1,0] ou [0,-1,1], [0,1,-1], [1,0,-1], [1,-1,0] , …
et surtout [-1,0,1] c'est le même que tu prennes le premier -1 du tableau ou le second …

[serpentcorail]

J'ai réussi ! j'ai remarqué que les solutions étaient des tableaux où les valeurs sont dans l'ordre, j'ai donc ordonné les triplets ça m'a donné plein de doublons et j'ai dédoublonné avec array_unique qui marche sur les tableau de tableau ( ouf ) et le output à été accepté , j'attend de comprendre bien l'énoncé avant de mettre résolu.

Je fait appel à une personne pédagogue , à votre bon cœur.

je met mon code , il n'est pas beau , il à une complexité de en n3 etc .. je sais

merci de tout aide cordialement

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function threeSum($nums) {
 
       $o =0 ;
 
       for ($i=0;$i<count($nums);$i++){          
          for ($j=0;$j<count($nums);$j++){             
               for ($k=0;$k<count($nums);$k++){                      
 
                     if ($k != $j && $i != $j && $k !=  $i){                        
 
                        if ($nums[$i] + $nums[$j] + $nums[$k] === 0){                          
 
                         $tab[0] = $nums[$i];
                         $tab[1] = $nums[$j];
                         $tab[2] = $nums[$k];                        
 
                         sort($tab);                         
 
                         $res[$o] = [ $tab[0],$tab[1],$tab[2] ] ;
 
                         $o++;           
 
                     }
                   }
 
 
              }
           }
         } 
 
 
      return array_unique($res,SORT_REGULAR);  
 
    }
}

maintenant la dernière étape c'est de retourner [] si le input est [0] ou [] ,

la condition que j'ai écrite est

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
if( ( ! empty($nums) ) || !(  (count($num) == 1 ) &&    ($num[0] == 0) )  ){   
 
 
//faire le traitement
 
}else{
 
 
// retourner []
 
}

mais j'ai une erreur quand le input est []

des lanternes ?

[Flodelarab]

Bonjour

Sans vouloir être désagréable, c'est ce code qui ne va pas :

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for ($i=0;$i<count($nums);$i++){
for ($j=0;$j<count($nums);$j++){
for ($k=0;$k<count($nums);$k++){

On préférera :

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for ($i=0;$i<count($nums);$i++){
for ($j=$i+1;$j<count($nums);$j++){
for ($k=$j+1;$k<count($nums);$k++){

Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.

[WhiteCrow]

[...]

Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.

Attention aux cas comme [-1, -1, -1, 2] qui malgré les nouvelles initialisations de boucles donneront des doublons …

[serpentcorail]

merci je vais tester tout ça

[serpentcorail]

Bonjour

Sans vouloir être désagréable, c'est ce code qui ne va pas :

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for ($i=0;$i<count($nums);$i++){
for ($j=0;$j<count($nums);$j++){
for ($k=0;$k<count($nums);$k++){

On préférera :

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for ($i=0;$i<count($nums);$i++){
for ($j=$i+1;$j<count($nums);$j++){
for ($k=$j+1;$k<count($nums);$k++){

Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.

salut , j'avais pensé à ça au début mais j'aime bien faire compliqué lol

tu veux dire comme ça ?

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function threeSum($nums) {               
 
      for ($i=0;$i<count($nums);$i++){
      for ($j=$i+1;$j<count($nums);$j++){
      for ($k=$j+1;$k<count($nums);$k++){               
 
                     if ($nums[$i] + $nums[$j] + $nums[$k] === 0){                                
 
$tab[0] = $nums[$i];
$tab[1] = $nums[$j];
$tab[2] = $nums[$k];
 
sort($tab);
 
$res[$o] = [ $tab[0],$tab[1],$tab[2] ] ;
 
$o++;                 
                     }
 
 
 
       }}} 
 
 
 
      return $res;    
 
 
    }
}

mais ça retourne un doublon quand même , peut tu me dire pk ?
une condition qui manque ?

[Flodelarab]

Attention aux cas comme [-1, -1, -1, 2] qui malgré les nouvelles initialisations de boucles donneront des doublons …

Tu as raison sur le fait que le dédoublonnage est quand même nécessaire. Par contre, ton exemple n'est pas bon. Il y a plusieurs [-1;0;1], mais il y a un seul [-1, -1, 0, 2]. Quant à [-1, -1, -1, 2], la somme ne fait pas 0.

mais ça retourne un doublon quand même , peut tu me dire pk ?

Car -1 est présent 2 fois dans ton tableau. Empêcher les doublons d'indices n'empêche pas les doublons de valeurs.

[WhiteCrow]

Tu as raison sur le fait que le dédoublonnage est quand même nécessaire. Par contre, ton exemple n'est pas bon. Il y a plusieurs [-1;0;1], mais il y a un seul [-1, -1, 0, 2]. Quant à [-1, -1, -1, 2], la somme ne fait pas 0.

[-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]
Une de mes idées de départ (la seconde) était en fait de non seulement trier le tableau d'origine mais de ne garder au maximum que 2 exemplaire de chaque nombre (avec le cas du triple 0 qui convient comme solution et qu'il faut traiter à part). Le tri en n×log n, le filtrage en n et la recherche en n² donne un bon algo avec un complexité spatiale en n tout de même … je pense qu'on peut réduire cette complexité spatiale en O(1) …

[Flodelarab]

[-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]

Et non. Toujours pas. Car pour obtenir 2 fois [-1,-1,2], il faudrait tirer 2 fois les indices 0, 3 et 4, ce qui est impossible.
Le bon contre-exemple est bien celui que j'ai donné : [-1, 0,1]. Car comme il y a 2 valeurs -1, on ne peut pas éviter le tirage des indices (0;1;2) et (1;2;4). C'est là que le doublon apparaît.

[serpentcorail]

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:

Input: nums = []
Output: []
Example 3:

Input: nums = [0]
Output: []



maintenant ça bloque pour le deuxième cas si le tableau est vide je fais un return []; mais le site le rejette , j'obtiens une erreur comme si le type attendu ne correspondais pas

[Flodelarab]

Quel langage de programmation ?

[WhiteCrow]

[-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]

Et non. Toujours pas. Car pour obtenir 2 fois [-1,-1,2], il faudrait tirer 2 fois les indices 0, 3 et 4, ce qui est impossible.
Le bon contre-exemple est bien celui que j'ai donné : [-1, 0,1]. Car comme il y a 2 valeurs -1, on ne peut pas éviter le tirage des indices (0;1;2) et (1;2;4). C'est là que le doublon apparaît.

Bon je vais parler plus simplement :

A=[-1, -1, -1, 2 ]
i=0, j=1, k=2 → [-1, -1, -1] → Σ=-3 pas une solution
i=0, j=1, k=3 → [-1, -1, 2] → Σ=0 une solution !
i=1, j=2, k=3 → [-1, -1, 2] → Σ=0 une solution mais en double … avec des éléments qui n'ont pas les même indices …

[serpentcorail]

Quel langage de programmation ?

C'est le même test de début du post , c'est en PHP , quand le input est [] ou [0] ça doit retourner [] c'est un tableau nulle je suppose un var_dump donne NULL , mais le compilo, je veux dire l'interpréteur , pardon, de de Leetcode me refuse ça