讨论/技术交流/【每日一题:平方数之和】转换为「两数之和」的二分搜索解法/
【每日一题:平方数之和】转换为「两数之和」的二分搜索解法

前言

官方题解的最优方法「费马平方和」确实想不到(这个应该属于没看过就确实想不出来的那种),次优解「双指针」的做法我看了之后发现也比较取巧,所以这里贴一下我的朴实思路,仅供参考。

看到题之后第一想到枚举,也就是固定aa,去枚举bb,也就是官方的第一种解法,之后想到能不能用二分搜索优化一下,于是联想到力扣的第一道题【两数之和】,于是有了下面的解法。

解题思路

  1. 生成数组arr:元素值为从0到c\sqrt{c}所有值的平方数,也就是02,12,22...n20^2,1^2,2^2...n^2,其中n=cn=\sqrt{c}
  2. 「两数之和」:设第一个数为a2a^2,那么二分查找的目标就是ca2c-a^2,也就是b2b^2

由于第一个步骤生成的数组是有序的,所以第二个数的查找可以优化,JavaScript代码如下:

代码

var judgeSquareSum = function(c) {
    const big = Math.floor(Math.sqrt(c));

    const arr = new Array(big+1).fill(0);
    arr.forEach((v, i) => arr[i] = i*i);

    for (let i=0; i<big+1; ++i) {
        const tar = c - arr[i];

        let left = i;
        let right = big;
        while (left <= right) {
            const mid = left + (right - left >> 1);
            if (arr[mid] === tar) {
                return true;
            } else if (arr[mid] < tar) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return false;
};

理论时间复杂度是O(clog(c))O(\sqrt{c}*log(\sqrt{c})),有额外O(c)O(\sqrt{c})的空间复杂度(这个应该可以优化,只追踪两个端点就好了),不过为了直观还是这样写。

小白见解,欢迎讨论~

共 0 个回复
暂无回复