花花酱 LeetCode 1925. Count Square Sum Triples

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

Constraints:

Solution: Enumerate a & b

Brute force enumerates a & b & c, which takes O(n³). Just need to enumerate a & b and validate c.

Time complexity: O(n²)
Space complexity: O(1)

// Author: Huahua

class Solution {

public:

int countTriples(int n) {

int ans = 0;

for (int a = 1; a <= n; ++a)

for (int b = 1; b <= n; ++b) {

int c = sqrt(a * a + b * b);

if (c <= n && c * c == a * a + b * b) ++ans;

}

return ans;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏