寒光博客

[LeetCode]633. 平方数之和
题目 给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c。 示例1: 输入...
扫描右侧二维码阅读全文
21
2020/06

[LeetCode]633. 平方数之和

题目

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

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

 

示例2:

输入: 3
输出: False

链接:https://leetcode-cn.com/problems/sum-of-square-numbers

解析

可以看成是在元素为 0~target 的有序数组中查找两个数,使得这两个数的平方和为 target,如果能找到,则返回 true,表示 target 是两个整数的平方和。

本题和 167. Two Sum II - Input array is sorted 类似,只有一个明显区别:一个是和为 target,一个是平方和为 target。本题同样可以使用双指针得到两个数,使其平方和为 target。

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

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

代码

 public boolean judgeSquareSum(int c) {
        int i = 0;
        int j = (int) Math.sqrt(c);//j的上限
        if (c < 0)
            return false;
        while (i <= j) {//双指针 等号是 同一个数字
            int mul = i * i + j * j;
            if (mul < c) i++;
            else if (mul > c)
                j--;
            else return true;
        }
        return false;
    }

笔记

双指针解法 类同1和167
忘记i j 有可能是同一个数字 比如2

本文作者:Author:     文章标题:[LeetCode]633. 平方数之和
本文地址:http://dxoca.cn/Algorithm/358.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:June 21st, 2020 at 03:35 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment