每日一题2021/4/28：平方数之和

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

class Solution {
public:
    bool judgeSquareSum(int c) {
        if(c <= 2)
            return true;
        else{
            int p = 3;
            
            while(p <= c){
                int a = 0;
                while(c % p == 0){
                    a++;
                    c /= p;
                }
                if((p % 4 == 3) && (a % 2 == 1))
                    return false;
                p += 2;
            }
            if(c % 4 == 3)
                return false;
            else
                return true;

        }
    }
};
           

此处使用的方法是数论中的一个定理：对于可以拆分为两个平方数之和的整数，其（4k+3）型质因子的幂次必定是偶数次的。因此我们只需要遍历此类质因子即可判断c是否满足题意。其中，p+=2而不是+4或者单独计算p是否为质数的原因是一方面可以加速程序运行（程序执行当中直接判断能否整除，不会消耗过多资源，如果先判断是否是质数反而浪费计算资源，并且+2虽然会考虑到(4k+1)型质因子但是可以缩小c的规模大大加速程序的运行速度）但是，题解中的方法选择的外层while循环条件为p*p<=c并不是很理解，可能是程序断点设计的有缺陷。

此外，此题用计算机思路解法的话应当是双指针，明天起除每日一题外将单独写一篇双指针的博客来研究。

bool judgeSquareSum(int c){
    int A=0;
    int B=sqrt(c);
    long squareA=0;
    long squareB=B*B;

    while(A<=B){
        int ret = squareA+squareB-c;
        if(0==ret){
            return true;
        }else if(ret<0){
            //(x+1)^2=x^2+2*x+1
            squareA=squareA+(A<<1)+1;
            A++;
        }else{   
            //(x-1)^2=x^2-2*x+1
            squareB=squareB-(B<<1)+1;
            B--;
        }
    }
    
    return false;
}
           

双指针的本质是矩阵中元素的移动，对于f(a, b)这类递增函数来说，如果a,b有序则可以选择一头一尾，这样初始化的元素在矩阵的左上角，从而慢慢逼近目标。