Vison's Blog
所有文章
文章总览
编辑器
Publications
About Me
Search
目录
#toc-container
下载Markdown文件
【4.28】LeetCode每日一题· 平方数之和
2021年04月28日 10时43分
标签：
LeetCode
模拟
数学
## 题目描述 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得$$a^2 + b^2 = c$$。 #### 示例1 ``` 输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5 ``` #### 示例2 ``` 输入：c = 3 输出：false ``` #### 示例3 ``` 输入：c = 4 输出：true ``` #### 示例4 ``` 输入：c = 2 输出：true ``` #### 示例5 ``` 输入：c = 1 输出：true ``` #### 提示 ``` 0 <= c <= 2^31 - 1 ``` #### 来源 > 来源：力扣（LeetCode） > 链接：[题目链接](https://leetcode-cn.com/problems/sum-of-square-numbers/ "题目链接") ## 解题思路 从`0~sqrt(c)`遍历`a`，判断`b = c - a*a`是否是平方数。如果`b`是平方数，则有`b = (int)sqrt(b) * (int)sqrt(b)`，这样可以在$$O(\\sqrt c)$$时间内完成任务。 注意，为了防止`a*a`溢出，需要将`a`设置或者强制类型转换为`long long`再和`c`比较大小，判断循环边界。 ## 代码 ```cpp class Solution { public: bool judgeSquareSum(int c) { for(long long a = 0; a*a <= (long long)c; a++){ int b = sqrt(c - a*a); if(b*b == c-a*a){ return true; } } return false; } }; ``` ### 用时和内存 > 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户 > 内存消耗：5.7 MB，在所有 C++提交中击败了84.36%的用户
所有评论
暂无评论
新增评论
评论
邮箱
邮箱仅作验证使用
图形验证码
邮箱验证码
发送验证码
发表评论
所有评论
暂无评论