What is a square triple?

A square triple (a, b, c) is a set of three integers where a² + b² = c², meaning the sum of the squares of a and b equals the square of c.

How do I optimize this problem?

You can optimize the brute force solution by precomputing squares, reducing the number of calculations, and eliminating redundant checks for pairs like (a, b) and (b, a).

How does GhostInterview assist with solving the problem?

GhostInterview helps by providing structured advice on mathematical enumeration, ensuring efficient handling of the problem's complexity and common pitfalls.

Why is it important to check if a² + b² is a perfect square?

Checking if a² + b² is a perfect square is crucial because the problem asks for valid triples where the sum of squares of a and b equals c², making the square root check essential.

What other problems are similar to Count Square Sum Triples?

Problems involving pairs, squares, and summation such as finding Pythagorean triples or those requiring enumeration over number ranges share similar techniques and patterns.

#1925

Easy

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

统计平方和三元组的数目

一个平方和三元组 (a,b,c) 指的是满足 a 2 + b 2 = c 2 的整数三元组 a ， b 和 c 。给你一个整数 n ，请你返回满足 1 的平方和三元组的数目。示例 1：输入： n = 5 输出： 2 解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。示例…

数学枚举

题目描述

一个 平方和三元组 (a,b,c) 指的是满足 a² + b² = c² 的整数三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

提示：

1 <= n <= 250

lightbulb

解题思路

方法一：枚举

我们在 $[1, n)$ 的范围内枚举 $a$ 和 $b$ ，然后计算 $c = \sqrt{a^2 + b^2}$ ，如果 $c$ 是整数且 $c \leq n$ ，那么就找到了一个平方和三元组，答案加一。

枚举结束后，返回答案即可。

时间复杂度 $O(n^2)$ ，其中 $n$ 是给定的整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countTriples(self, n: int) -> int:
        ans = 0
        for a in range(1, n):
            for b in range(1, n):
                x = a * a + b * b
                c = int(sqrt(x))
                if c <= n and c * c == x:
                    ans += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands the concept of square triples and can break the problem into smaller, manageable parts.
question_mark
The candidate demonstrates the ability to optimize brute force methods by applying mathematical properties.
question_mark
The candidate shows attention to detail in ensuring that each valid pair is counted only once.

warning

常见陷阱

外企场景

error
Failing to account for the fact that (a, b) and (b, a) represent the same triple, leading to double-counting.
error
Neglecting to check that the square root of a² + b² is an integer and not just a floating-point value.
error
Not handling the edge cases where n is small or large, leading to either incorrect answers or inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the problem for n up to a much larger value, e.g., 1000, and see how the solution needs to scale.
arrow_right_alt
Modify the problem to only count distinct triples (a, b, c) without considering the order of a and b.
arrow_right_alt
Extend the problem to check if a² + b² + c² = d² for four variables, increasing the complexity.

help

常见问题

外企场景

继续练习

#1952 三除数 #1863 找出所有子集的异或总和再求和 #2048 下一个更大的数值平衡数