[数据结构与算法]leetcode记录-633-平方数之和

633.平方数之和

思路

如果存在两个数平方和等于c，这两个数一定小于根号c取整（设为a），因此左指针l取0（0莫忘），右指针r取a，若平方和小于c，l++，大于c，r++，等于c，返回true。

代码

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
}

技巧和总结

1. int型尽量用long。
2. 求c平方根，取整：long right = (long) Math.sqrt(c);。
3. 双指针为什么不会错过正确答案：因为如果存在一定在0-a之间，当l和r平方和小于c，因为当前最大的r已不能满足l，小的r更别说，所以需要l++；当平方和大于c，除掉所有排除的组合，此时r太大，最小的l一起都太大，更别说大的l，所以排除所有与当前r组合的情况，r–。每次排除一系列组合都是不可能的，如果存在，其一定没被排除，不断缩小空间总会到它。—— 矩阵搜索空间更容易看。