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

提示：

0 <= c <= 231 - 1

题解

1. 原本的思路是从 0 开始遍历到 c，结果一直显示超时，但是通过评论找到一个思路，就是从 0 遍历 c 的平方根，这样就不会超时了。遍历的时候，通过解平方根去寻找这个值是否为整数。

TIP

执行用时：68 ms, 在所有 JavaScript 提交中击败了 99.62% 的用户
内存消耗：37.5 MB, 在所有 JavaScript 提交中击败了 28.77% 的用户

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    let count = Math.floor(Math.sqrt(c)) // 获取遍历的范围，因为要寻找的那个值肯定不会超过 c 的平方根
    for(let i=0;i<=count;i++) {
        // val 为要寻找的值
        let val = Math.sqrt(c - Math.pow(i,2))
        // 如果 val 与 取整后相等，说明寻找到了这个值
        if(val === Math.trunc(val)) return true
    }

    return false
};

• 时间复杂度： `O(根号n)`，遍历从 0 到 c的平方根
• 空间复杂度： `O(1)`，使用了两个变量来储存值
• 最好情况： 较早的获取到值，则直接退出遍历
• 最坏情况： 没有找到值，那么需要遍历结束

2. 利用双指针来寻找值

TIP

执行用时：96 ms, 在所有 JavaScript 提交中击败了 46.74% 的用户
内存消耗：39.1 MB, 在所有 JavaScript 提交中击败了 19.18% 的用户

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    // i 为左指针
    // j 为右指针
    let i=0;j=Math.floor(Math.sqrt(c));s = 0
    while(i<=j) {
        // s 用来储存相加的结果
        s = Math.pow(i, 2) + Math.pow(j, 2)
        if(s === c) return true
        // 如果相加的结果比 c 大，说明右指针需要往左移动
        // 否则，左指针往右移动
        s > c ? j-- : i++
    }

    return false
};

• 时间复杂度： `O(n)`，一个 while循环
• 空间复杂度： `O(1)`，使用了三个变量来储存值
• 最好情况： 较早的获取到值，则直接退出遍历
• 最坏情况： 没有找到值，那么需要遍历结束