题目链接

455. 分发饼干 - 力扣（LeetCode）

题目描述

对于给定的非负整数c，判断是否存在整数a和b，使得a^2+b^2 = c^2。

输入输出样例

1
2
3
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

代码

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/assign-cookies/solutions/534281/fen-fa-bing-gan-by-leetcode-solution-50se/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// sqrt
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
};

// 双指针
class Solution {
public:
    bool judgeSquareSum(int c) {
        long a = 0, b = (long)sqrt(c);
        while (a <= b) {
            long sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
};