Problema
Encontre todas as triplas de inteiros positivos a < b < c para as quais a² + b² = c² e a + b + c = perimeter. Retorne cada tripla como [a, b, c], ordenadas por a crescente e depois b. Não inclua permutações dos mesmos lados.
Implemente pythagorean_triplets(perimeter).
Entrada
perimeter: A soma exigida dos três lados.
Saída
Retorne uma lista de triplas na ordem especificada.
Restrições
3 ≤ perimeter ≤ 100.000. Retorne uma lista vazia se nenhum triângulo atender aos critérios.
Exemplos
Entrada:
perimeter = 30
Saída esperada:
expected = [
[5, 12, 13]
]Entrada:
long long perimeter = 30;
Saída esperada:
std::vector<std::vector<long long>> expected = {
{5, 12, 13}
};Entrada:
long perimeter = 30;
Saída esperada:
long[][] expected = new long[][] {
new long[] {5, 12, 13}
};Explicação
5 + 12 + 13 = 30 e 5² + 12² = 13². Esta é a única tripla que atende aos requisitos.
Entrada:
perimeter = 11
Saída esperada:
expected = []Entrada:
long long perimeter = 11;
Saída esperada:
std::vector<std::vector<long long>> expected = {};Entrada:
long perimeter = 11;
Saída esperada:
long[][] expected = new long[][] {};Explicação
Nenhuma tripla crescente de inteiros positivos de triângulo retângulo soma 11.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Um trio válido precisa satisfazer tanto a equação de Pitágoras quanto a soma do perímetro.
Dica 2
Use o perímetro para limitar a busca em vez de tentar toda ordem possível dos lados.
Dica 3
Lembre de manter apenas a b c e ignore duplicatas vindas de escolhas simétricas dos lados.
Complexidade esperada
tempo O(n^2), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.