2021-05-04：给定一个非负整数c，你要判断是否存在两个整数a和b，使得a*a+b*b=c。【举例】c=5时，返回true。c=4时，返回true。c=3时，返回false。

2021-05-04：给定一个非负整数c，你要判断是否存在两个整数a和b，使得aa+bb=c。【举例】c=5时，返回true。c=4时，返回true。c=3时，返回false。

福大大 答案2021-05-04：

四平方和定理。时间复杂度：O(sqrt(N))。空间复杂度：O(1)。
1.n一直除以4，直到不能整除为止。
2.n%8,如果余7，直接返回4。
3.从1到sqrt(n)开始循环，aa+bb=c成立时，a和b都不为0，返回2;a和b有一个为0，返回1。
4.返回3。
5.在本题中，返回值是1和2的是true。返回值是3和4的是false。

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math"

)

func main() {

    for i := 1000; i <= 1100; i++ {

        ret := isSquares(i)

        fmt.Println(i, ret)

    }

}

//4+1+1+1

func isSquares(n int) bool {

    return numSquares(n) <= 2

}

func numSquares(n int) int {

    for n&3 == 0 { //n%4==0

        n >>= 2 //n/=4

    }

    if n&7 == 7 { //n%8==7

        return 4

    }

    a := 0

    for a*a <= n {

        b := int(math.Sqrt(float64(n - a*a)))

        if a > b {

            break

        }

        if a*a+b*b == n {

            ret := 0

            if a != 0 {

                ret++

            }

            if b != 0 {

                ret++

            }

            return ret

        }

        a += 1

    }

    return 3

}

执行结果如下：

2021-05-04：给定一个非负整数c，你要判断是否存在两个整数a和b，使得a*a+b*b=c。【举例】c=5时，返回true。c=4时，返回true。c=3时，返回false。的相关教程结束。