Problème
Trouvez tous les triplets d'entiers positifs a < b < c tels que a² + b² = c² et a + b + c = perimeter. Retournez chaque triplet sous la forme [a, b, c], triés par ordre croissant de a puis de b. N'incluez pas les permutations des mêmes côtés.
Implémentez pythagorean_triplets(perimeter).
Entrée
perimeter : La somme requise des trois côtés.
Sortie
Retournez une liste des triplets dans l'ordre spécifié.
Contraintes
3 ≤ perimeter ≤ 100 000. Retournez une liste vide si aucun triangle ne convient.
Exemples
Entrée :
perimeter = 30
Sortie attendue :
expected = [
[5, 12, 13]
]Entrée :
long long perimeter = 30;
Sortie attendue :
std::vector<std::vector<long long>> expected = {
{5, 12, 13}
};Entrée :
long perimeter = 30;
Sortie attendue :
long[][] expected = new long[][] {
new long[] {5, 12, 13}
};Explication
5 + 12 + 13 = 30 et 5² + 12² = 13². C'est le seul triplet qui convient.
Entrée :
perimeter = 11
Sortie attendue :
expected = []Entrée :
long long perimeter = 11;
Sortie attendue :
std::vector<std::vector<long long>> expected = {};Entrée :
long perimeter = 11;
Sortie attendue :
long[][] expected = new long[][] {};Explication
Aucun triplet croissant d'entiers positifs formant un triangle rectangle ne donne une somme de 11.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Un triplet valide doit vérifier à la fois l’équation de Pythagore et la somme du périmètre.
Indice 2
Utilise le périmètre pour limiter la recherche au lieu d’essayer tous les ordres possibles des côtés.
Indice 3
N’oublie pas de garder seulement a < b < c, et d’ignorer les doublons dus aux choix symétriques des côtés.
Complexité attendue
temps O(n^2), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.