leetcode--双指针2（633题/medium/cpp）

leetcode

按照模块刷题，点击进入使用的刷题目录

双指针

2.平方数之和

题目描述：

633.平方数之和

解题思路： 本题的关键在于找到初始上界，实现剪枝（通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝），从而降低时间复杂度。将low、high分别初始化为0和sqrt©，计算low^2 +high^2的值，若大于c则–high，小于c则++low。

代码：

class Solution {
public:
    bool judgeSquareSum(int c) {
        if(c<0) return false;
        long low=0,high=(int)sqrt(c);
        long sum=0;
        while(low<=high){
            sum=low*low+high*high;
            if(sum>c){
                --high;
            }
            else if(sum<c){
                ++low;
            }
            else{
                return true;
            }
        }
        return false;
    }
};
           

改进： 一开始变量low,high,sum用的是int型，大的测试用例一直执行出错，改成long型后运行通过。