【每日算法】平方数之和

本文最后更新于：2024年11月17日 晚上

663.平方数之和

tag:数学 双指针 二分查找

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

示例 1：

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

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    let a = 0,b = Math.floor(Math.sqrt(c))

    while(a<=b){
        const s = a*a+b*b
        if(s===c) return true

        if(s<c){
            a++
        }else{
            b--
        }
    }
    return false
};

思路：

这个题目其实和两数之和类似，使用相向双指针来解决，看成给定一个[0,…..,c]的数组，找出两个数满足： a+b=c

一个指针p1指向头arr[0] ,一个指针p2指向尾arr[arr.length-1],因为数组是有序的，判断a+b是否大于，如果大于的话p2–，否则p1–

复杂度

时间复杂度：O(c开根号)

空间复杂度：O(1)