【Day02】633.平方数之和

题目:

给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = 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

枚举

对 a 从 0 开始到 n√n 枚举,然后判断是否存在 b。

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i = 0; (long long)(i) * i <= c; i++) {
            int j = sqrt(c - i * i);
            if (i * i + j * j == c)
                return true;
        }
        return false;
    }
};

预处理+查询

如果存在符合条件的a,b,那么a和b一定在1和sqrt(c)之间。

class Solution {
public:
    typedef unsigned long long ULL;
    bool judgeSquareSum(int c) {
        if (c == 0) return true;
        unordered_map um;
        for (int i = 1; i <= sqrt(c); i++) {
            um[i*i]++;
        }

        for (int i = 1; i <= sqrt(c); i++) {
            if (i*i == c || um.count(c - i*i)) return true;
        }
        return false;
    }
};

双指针

class Solution {
public:
    bool judgeSquareSum(int c) {
        int j = sqrt(c);
        int i = 0;
        while (i <= j) {
            if (i*i > c - j*j) {
                j--;
            } else if (i*i < c - j*j) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
};

   转载规则


《【Day02】633.平方数之和》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day03】403.青蛙过河 【Day03】403.青蛙过河
403. 青蛙过河题目描述: 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示)
2021-04-29
下一篇 
【Day01】938.二叉搜索树的范围和 【Day01】938.二叉搜索树的范围和
最近决定巩固一下算法,开始刷leetcode每日一题,具体刷多久还不知道,刚开始是有点吃力,慢慢来。 【Day01】938.二叉搜索树的范围和题目: 给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的
2021-04-27
  目录