LeetCode 1925: Count Square Sum Triples (Pythagorean Enumeration with Square Set)
LeetCode 1925MathEnumerationToday we solve LeetCode 1925 - Count Square Sum Triples.
Source: https://leetcode.com/problems/count-square-sum-triples/
English
Problem Summary
Given an integer n, count ordered triples (a, b, c) such that 1 <= a, b, c <= n and a² + b² = c². Because the triples are ordered, (a, b, c) and (b, a, c) are counted separately when a != b.
Key Insight
Instead of trying to solve c = sqrt(a² + b²) with floating-point checks each time, precompute all perfect squares up to n² in a boolean table. Then each pair (a, b) can be verified in O(1) time by checking whether a² + b² is in the square table.
Brute Force and Why We Improve
A direct brute force loops all a, b, c (three nested loops) and checks the equation, which is O(n³). We can reduce one loop by pre-indexing valid squares, giving an O(n²) method that is cleaner and faster.
Optimal Algorithm (Step-by-Step)
1) Build isSquare[x] for all x = c², where 1 <= c <= n.
2) Enumerate a from 1 to n, and b from 1 to n.
3) Compute sum = a² + b².
4) If sum <= n² and isSquare[sum] is true, increment answer.
Complexity Analysis
Time: O(n²).
Space: O(n²) for the square lookup table.
Common Pitfalls
- Forgetting ordered semantics and accidentally forcing a < b.
- Using floating-point square-root comparisons that may introduce precision corner cases.
- Missing sum <= n² boundary before reading the lookup table.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countTriples(int n) {
boolean[] isSquare = new boolean[n * n + 1];
for (int c = 1; c <= n; c++) {
isSquare[c * c] = true;
}
int ans = 0;
for (int a = 1; a <= n; a++) {
int a2 = a * a;
for (int b = 1; b <= n; b++) {
int sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
ans++;
}
}
}
return ans;
}
}func countTriples(n int) int {
isSquare := make([]bool, n*n+1)
for c := 1; c <= n; c++ {
isSquare[c*c] = true
}
ans := 0
for a := 1; a <= n; a++ {
a2 := a * a
for b := 1; b <= n; b++ {
sum := a2 + b*b
if sum <= n*n && isSquare[sum] {
ans++
}
}
}
return ans
}class Solution {
public:
int countTriples(int n) {
vector<bool> isSquare(n * n + 1, false);
for (int c = 1; c <= n; ++c) {
isSquare[c * c] = true;
}
int ans = 0;
for (int a = 1; a <= n; ++a) {
int a2 = a * a;
for (int b = 1; b <= n; ++b) {
int sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
++ans;
}
}
}
return ans;
}
};class Solution:
def countTriples(self, n: int) -> int:
is_square = [False] * (n * n + 1)
for c in range(1, n + 1):
is_square[c * c] = True
ans = 0
for a in range(1, n + 1):
a2 = a * a
for b in range(1, n + 1):
s = a2 + b * b
if s <= n * n and is_square[s]:
ans += 1
return ansvar countTriples = function(n) {
const isSquare = new Array(n * n + 1).fill(false);
for (let c = 1; c <= n; c++) {
isSquare[c * c] = true;
}
let ans = 0;
for (let a = 1; a <= n; a++) {
const a2 = a * a;
for (let b = 1; b <= n; b++) {
const sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
ans++;
}
}
}
return ans;
};中文
题目概述
给定整数 n，统计满足 1 <= a, b, c <= n 且 a² + b² = c² 的有序三元组 (a, b, c) 数量。注意是有序三元组，所以当 a != b 时，(a, b, c) 与 (b, a, c) 都要计数。
核心思路
不要每次都通过开方判断 a² + b² 是否是完全平方数（浮点判断容易啰嗦）。先把 1..n 的平方预处理到布尔表 isSquare 中，之后每个 (a,b) 只需 O(1) 判断。
朴素解法与优化
朴素做法是三重循环枚举 a,b,c，复杂度 O(n³)。利用“平方值可预处理”这一点，可以把对 c 的枚举消掉，降为 O(n²)。
最优算法（步骤）
1）预处理 isSquare[c²] = true（1 <= c <= n）。
2）双重循环枚举 a、b。
3）计算 sum = a² + b²。
4）若 sum <= n² 且 isSquare[sum] 为真，则答案加一。
复杂度分析
时间复杂度：O(n²)。
空间复杂度：O(n²)（平方查表）。
常见陷阱
- 把题目当成无序对，只统计 a < b，会少算。
- 直接用浮点开方比较，代码可读性和稳定性都不如查表。
- 忽略 sum 上界检查，可能访问数组越界。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countTriples(int n) {
boolean[] isSquare = new boolean[n * n + 1];
for (int c = 1; c <= n; c++) {
isSquare[c * c] = true;
}
int ans = 0;
for (int a = 1; a <= n; a++) {
int a2 = a * a;
for (int b = 1; b <= n; b++) {
int sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
ans++;
}
}
}
return ans;
}
}func countTriples(n int) int {
isSquare := make([]bool, n*n+1)
for c := 1; c <= n; c++ {
isSquare[c*c] = true
}
ans := 0
for a := 1; a <= n; a++ {
a2 := a * a
for b := 1; b <= n; b++ {
sum := a2 + b*b
if sum <= n*n && isSquare[sum] {
ans++
}
}
}
return ans
}class Solution {
public:
int countTriples(int n) {
vector<bool> isSquare(n * n + 1, false);
for (int c = 1; c <= n; ++c) {
isSquare[c * c] = true;
}
int ans = 0;
for (int a = 1; a <= n; ++a) {
int a2 = a * a;
for (int b = 1; b <= n; ++b) {
int sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
++ans;
}
}
}
return ans;
}
};class Solution:
def countTriples(self, n: int) -> int:
is_square = [False] * (n * n + 1)
for c in range(1, n + 1):
is_square[c * c] = True
ans = 0
for a in range(1, n + 1):
a2 = a * a
for b in range(1, n + 1):
s = a2 + b * b
if s <= n * n and is_square[s]:
ans += 1
return ansvar countTriples = function(n) {
const isSquare = new Array(n * n + 1).fill(false);
for (let c = 1; c <= n; c++) {
isSquare[c * c] = true;
}
let ans = 0;
for (let a = 1; a <= n; a++) {
const a2 = a * a;
for (let b = 1; b <= n; b++) {
const sum = a2 + b * b;
if (sum <= n * n && isSquare[sum]) {
ans++;
}
}
}
return ans;
};
Comments