题目

一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 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

解题思路分析

1、暴力法；时间复杂度O(n^3)，空间复杂度O(1)

func countTriples(n int) int {
   res := 0
   for i := 1; i <= n; i++ {
      for j := 1; j <= n; j++ {
         for k := 1; k <= n; k++ {
            if i*i+j*j == k*k {
               res++
            }
         }
      }
   }
   return res
}

2、哈希辅助；时间复杂度O(n^2)，空间复杂度O(n)

func countTriples(n int) int {
   res := 0
   m := make(map[int]bool)
   for i := 1; i <= n; i++ {
      m[i*i] = true
   }
   for i := 1; i <= n; i++ {
      for j := 1; j <= n; j++ {
         if m[i*i+j*j] == true {
            res++
         }
      }
   }
   return res
}

3、内置函数；时间复杂度O(n^2)，空间复杂度O(1)

func countTriples(n int) int {
   res := 0
   for i := 1; i <= n; i++ {
      for j := 1; j <= n; j++ {
         k := int(math.Sqrt(float64(i*i + j*j)))
         if k*k == i*i+j*j && k <= n {
            res++
         }
      }
   }
   return res
}

总结

Easy题目，直接遍历即可