java 解法, 执行用时: 2 ms, 内存消耗: 39.3 MB, 提交时间: 2024-11-04 09:41:33

class Solution {
    public boolean judgeSquareSum1(int c) {
        for (int a = 0; a * a <= c / 2; a++) {
            int b = (int) Math.sqrt(c - a * a);
            if (a * a + b * b == c) {
                return true;
            }
        }
        return false;
    }

    // 双向双指针
    public boolean judgeSquareSum(int c) {
        int a = 0;
        int b = (int) Math.sqrt(c);
        while (a <= b) {
            if (a * a == c - b * b) { // 避免溢出
                return true;
            }
            if (a * a < c - b * b) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
}

python3 解法, 执行用时: 43 ms, 内存消耗: 16.6 MB, 提交时间: 2024-11-04 09:40:48

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a, b = 0, isqrt(c)
        while a <= b:
            s = a * a + b * b
            if s == c:
                return True
            if s < c:
                a += 1
            else:
                b -= 1
        return False


    # 枚举
    def judgeSquareSum2(self, c: int) -> bool:
        a = 0
        while a * a * 2 <= c:
            b = isqrt(c - a * a)
            if a * a + b * b == c:
                return True
            a += 1
        return False

rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-11-04 09:40:09

impl Solution {
    // 枚举
    pub fn judge_square_sum(c: i32) -> bool {
        for a in 0.. {
            if a * a > c / 2 {
                break;
            }
            let b = ((c - a * a) as f64).sqrt() as i32;
            if a * a + b * b == c {
                return true;
            }
        }
        false
    }

    // 双向双指针
    pub fn judge_square_sum2(c: i32) -> bool {
        let mut a = 0;
        let mut b = (c as f64).sqrt() as i32;
        while a <= b {
            if a * a == c - b * b {
                return true;
            }
            if a * a < c - b * b {
                a += 1;
            } else {
                b -= 1;
            }
        }
        false
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-08-19 12:57:14

func judgeSquareSum(c int) bool {
    for base := 2; base*base <= c; base++ {
        // 如果不是因子，枚举下一个
        if c%base > 0 {
            continue
        }

        // 计算 base 的幂
        exp := 0
        for ; c%base == 0; c /= base {
            exp++
        }

        // 根据 Sum of two squares theorem 验证
        if base%4 == 3 && exp%2 != 0 {
            return false
        }
    }

    // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
    // 因此在退出循环以后需要再做一次判断
    return c%4 != 3
}

golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2022-08-19 12:56:59

func judgeSquareSum(c int) bool {
    left, right := 0, int(math.Sqrt(float64(c)))
    for left <= right {
        sum := left*left + right*right
        if sum == c {
            return true
        } else if sum > c {
            right--
        } else {
            left++
        }
    }
    return false
}

golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2022-08-19 12:56:28

func judgeSquareSum(c int) bool {
    for a := 0; a*a <= c; a++ {
        rt := math.Sqrt(float64(c - a*a))
        if rt == math.Floor(rt) {
            return true
        }
    }
    return false
}