2021.9.27(LC)

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

• 如果存在符合条件的a，b，那么a和b一定在0和sqrt(c)之间。
• 最朴素的思路，两层for循环，从0到sqrt(c)，看是否存在符合条件的a和b。相当于遍历了两次从0到sqrt(c)。
• 显然，没有双指针快，双指针只需要遍历一次即可。为什么使用双指针不会把正确答案排除在外呢？我认为这才是需要认真考虑的问题，而不是双指针直接用。我们用a表示第一个数，b表示第二个数。从初始开始考虑，a = 0，b = (int)Math.sqrt(c)。
• if(a*a+b*b
• 反之，if(a*a+b*b>c)，b固定的情况下，当前所有能变化的a值，都不会满足条件，因此，当前的b也一定不在正确答案中。
• 综上，双指针法确保正确答案不会被排除。

思考：为什么使用双指针不会错过正确答案？为什么双指针不会错过正确答案？双指针的本质。