【LeetCode】633.平方數之和

• 題目描述

給定一個非負整數 c ，你要判斷是否存在兩個整數 a 和 b，使得

。

• 思路

雙指針。一個指向0，一個指向

，然後判斷兩個指針指向位置的平方和與c的大小，如果大于c值一定較大指針并行更小的數，否則移動較小指針指向更大的數。

• C++實作

class Solution {
public:
    // 雙指針
    bool judgeSquareSum(int c) {
        int i = 0, j = (int)sqrt(c);
        while(i<=j){
            int diff = c - i*i; // 防止溢出，使用減法
            if(diff>j*j){
                i++;
            }else if(diff<j*j){
                j--;
            }else
                return true;
        }
        return false;
    }
};