一、题目

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a + b = c 。

点击查看原题

二、思路

1）暴力+优化：

解题优先考虑能够做出来，首先想到的就是暴力搜索的方法，由于c已经知道，只需要暴力搜索a和b即可，搜索范围为。
对暴力搜索的优化：
很容易想到双重循环找a和b，这样会造成很多的时间浪费，由于，可以只用一次遍历b，不断对a用sqrt函数求解，并判断a是否有小数即可（通过强转类型再判断是否相等即可）

2）双指针

如果我们的双指针begin和end指向区间的头和尾，有三种情况需要考虑：

1）如果，直接返回true 2）如果，则begin = begin + 1 3）如果，则end = end - 1

三、代码

1）暴力优化

class Solution {
    public boolean judgeSquareSum(int c) {
        int n = (int)Math.sqrt(c);
        for (int a = n; a >= 0; a--) {
            double b = Math.sqrt(c - a*a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
}

时间复杂度为，空间复杂度为O(1)，但由于sqrt耗费时间较多，表现并不好。

2）双指针

class Solution {
    public boolean judgeSquareSum(int c) {
        int begin = 0, end = (int)Math.sqrt(c);
        while (begin <= end) {
            int val = begin * begin + end * end;
            if (val == c) {
                return true;
            }
            if (val < c) {
                begin++;
            } else {
                end--;
            }
        }
        return false;
    }
}

时间复杂度为，空间复杂度为O(1)，每个循环只有两次乘法运算，整体性能较好。