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型後運作通過。