LeetCode 633. 平方数之和

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
相似题目

题目描述

✅ 633. 平方数之和

思路分析

解法一：双指针（推荐）

核心思路：

设 i=0，j=floor(sqrt(c))。

若 i^2 + j^2 小于 c，增大 i；反之减小 j。

若存在相等则返回 true。

复杂度分析：

时间复杂度：O(sqrt(c))。

空间复杂度：O(1)。

class Solution {
    public boolean judgeSquareSum(int c) {
        long i = 0;
        long j = (long) Math.sqrt(c);

        while (i <= j) {
            long sum = i * i + j * j;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

import "math"

func judgeSquareSum(c int) bool {
	i := 0
	j := int(math.Sqrt(float64(c)))

	for i <= j {
		sum := i*i + j*j
		if sum == c {
			return true
		} else if sum < c {
			i++
		} else {
			j--
		}
	}
	return false
}

相似题目

题目	难度	考察点
633. 平方数之和	中等	双指针
367. 有效的完全平方数	简单	二分
69. x 的平方根	简单	二分
279. 完全平方数	中等	DP
100. 相同的树	简单	递归
18. 四数之和	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/34310134