Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Find Right-Triangle Triples

List all integer right triangles with a specified perimeter.

Das lernst du

  • List all integer right triangles for a perimeter
  • Avoid duplicates by ordering sides
  • Prune the search with bounds

Problem

Übersetzung anzeigen

Find every triple of positive integers a < b < c for which a² + b² = c² and a + b + c = perimeter. Return each triple as [a, b, c], ordered by increasing a and then b. Do not include permutations of the same sides.

Implement pythagorean_triplets(perimeter).

Input

perimeter: The required sum of all three sides.

Output

Return a list of triples in the specified order.

Einschränkungen

3 ≤ perimeter ≤ 100,000. Return an empty list if no triangle qualifies.

Beispiele

Beispiel 1
Eingabe:
perimeter = 30

Erwartete Ausgabe:
expected = [
    [5, 12, 13]
]
Eingabe:
long long perimeter = 30;

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
    {5, 12, 13}
};
Eingabe:
long perimeter = 30;

Erwartete Ausgabe:
long[][] expected = new long[][] {
    new long[] {5, 12, 13}
};

Erläuterung

5 + 12 + 13 = 30 and 5² + 12² = 13². This is the only qualifying triple.

Beispiel 2
Eingabe:
perimeter = 11

Erwartete Ausgabe:
expected = []
Eingabe:
long long perimeter = 11;

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {};
Eingabe:
long perimeter = 11;

Erwartete Ausgabe:
long[][] expected = new long[][] {};

Erläuterung

No increasing positive integer right-triangle triple sums to 11.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

A valid triple must satisfy both the Pythagorean equation and the perimeter sum.

Hinweis 2

Use the perimeter to limit the search instead of trying every ordering of sides.

Hinweis 3

Remember to keep only a < b < c, and skip duplicates from symmetric side choices.

Erwartete Komplexität

O(n^2) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 857 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.