开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode 633. 平方数之和

简介: LeetCode 633. 平方数之和
+关注继续查看

633. 平方数之和


给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 。


示例 1:


输入:c = 5
输出:true


解释:1 * 1 + 2 * 2 = 5


示例 2:


输入:c = 3
输出:false


示例 3:


输入:c = 4
输出:true
• 1
• 2


示例 4:


输入:c = 2
输出:true


示例 5:


输入:c = 1
输出:true


题解


右指针的初始化,实现剪枝,从而降低时间复杂度。设右指针为 x,左指针固定为 0,为了使 x的值尽可能接近 target,我们可以将 x 取为 sqrt(target)。


因为最多只需要遍历一次 0~sqrt(target),所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量,因此空间复杂度为 O(1)。


链接:https://leetcode-cn.com/problems/sum-of-square-numbers/solution/shuang-zhi-zhen-jie-ti-by-simple-zd-hj34/


代码


class Solution {
public:
    bool judgeSquareSum(int c) {
        long l=0,r=sqrt(c);
        int sum=0;
        while(l<=r)
        {
            sum=l*l+r*r;
            if(sum==c)
                return true;
            else if(sum>c)
                r--;
            else
                l++;        
        }
        return false;
    }
};

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
「leetCode」637-二叉树的层平均值⚡️
「leetCode」637-二叉树的层平均值⚡️
18 0
LeetCode20.有效的括号——纯C
LeetCode20.有效的括号——纯C
26 0
LeetCode 最接近的三个数之和
本题和盛水最多的容器这个题目非常的类似,我就不做过多的铺垫了,我们一起来看题目和我的解题思路吧。
19 0
​LeetCode刷题实战368:最大整除子集数
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
32 0
​LeetCode刷题实战301: 删除无效的括号
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
84 0
​LeetCode刷题实战16: 最接近的三数之和
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
13 0
​LeetCode刷题实战263:丑数
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
24 0
LeetCode解题之十六:最大子序和
LeetCode解题之十六:最大子序和
29 0
【leetcode刷题】33.最小的k个数——Java版
⭐欢迎订阅《leetcode》专栏,每日一题,每天进步⭐ 先找到第k小的数,然后遍历一遍数组,把所有比k小的数加入结果集。然后用这个数填充结果集,使结果集大小等于k。 ——leetcode此题热评
50 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载