Найти число пифагорейских троек в списке, используя python?

Question

Я кодирую решение для задачи, в которой код найдет число пифагорейских троек в списке, заданном списком a.Тем не менее, когда я отправляю свой код авто-грейдеру, есть некоторые тестовые случаи, когда мой код дает сбой, но я понятия не имею, что пошло не так.Пожалуйста, помогите мне указать на мою ошибку .....

def Q3(a):
    lst = [i ** 2 for i in a]
    lst.sort()
    ans = 0

    for x in lst:
        for y in lst:
            if (x + y) in lst:
                ans += 1

    return ans // 2

"Тройки Пифагора" являются целочисленными решениями теоремы Пифагора, например, 32 + 42 = 52.Учитывая список натуральных чисел, найдите количество пифагорейских триплетов.Два пифагорейских триплета различны, если хотя бы одно целое число отличается.

Реализация

· Реализация функции Q3 (A), где A - это список натуральных чисел.Размер списка A до 250.

· В списке нет дубликатов A

· Эта функция возвращает число пифагорейских триплетов.

Образец

· Q3 ([3,4,6,5]) = 1

· Q3 ([4,5,6]) = 0

Answer 1

Учитывая ограничения входных данных, которые вы сейчас добавили в свой вопрос с помощью редактирования, я не думаю, что с вашей реализацией что-то логически не так.Единственный тип тестов, которые ваш код может не пройти, должен быть связан с производительностью, поскольку вы используете одно из самых медленных решений, используя 3 вложенных цикла, повторяющихся по всему диапазону списка (реализован сам оператор in).с циклом).

Поскольку список отсортирован, и мы хотим x < y < z, мы должны сделать y начинать с x + 1 и z начинать с y + 1.И поскольку для x значение x зависит от значения y, для каждого данного y мы можем увеличивать z до тех пор, пока z * z < x * x + y * y больше не будет удерживаться, и если z * z == x * x + y * y при этомДело в том, что мы нашли пифагорейскую тройку.Это позволяет y и z проходить значения выше x только один раз и, следовательно, сокращает временную сложность с O (n ^ 3) до O (n ^ 2), делая его примерно в 40 раз быстрее, когда размериз списка 250:

def Q3(a):
    lst = [i * i for i in sorted(a)]
    ans = 0
    for x in range(len(lst) - 2):
        y = x + 1
        z = y + 1
        while z < len(lst):
            while z < len(lst) and lst[z] < lst[x] + lst[y]:
                z += 1
            if z < len(lst) and lst[z] == lst[x] + lst[y]:
                ans += 1
            y += 1
    return ans

Answer 2

Проблема 1: Предположим, что вы вводите

[3,4,5,5,5]

Хотя в вашем вопросе несколько неясно, я предполагаю, что это должно считаться тремя пифогорейскими тройками, каждая из которых использует одну из трех 5.

Ваша функция будет возвращать только 1.

Проблема 2. Как указывает Сэйс, ваша «тройка» может пытаться использовать одно и то же число дважды.

Было бы лучше использоватьitertools.combinations для получения различных комбинаций из списка квадратов и подсчета количества подходящих троек.

from itertools import combinations

def Q3(a):
    squares = [i**2 for i in a]
    squares.sort()
    ans = 0

    for x,y,z in combinations(squares, 3):
        if x + y == z:
            ans += 1

    return ans