【题目描述】
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c。
【示例1】
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
【示例2】
输入: 3
输出: False
【思路1】
1、暴力枚举 从0-c，是否存在两个数的平方和=c
2、时间复杂度O(n^2)
3、空间复杂度O(1)
4、超出时间限制
代码实现：
func judgeSquareSum(_ c: Int) -> Bool {
if c == 0 { return true }
for i in 0..<c {
for j in i..<c {
if i*i + j*j == c {
return true
}
}
}
return false
}
【思路2】
1、使用集合Set
2、判断set是否包含c-ii，如果包含返回true 否则把ii加到set里，直到遍历结束
3、时间复杂度O(n)
4、空间复杂度O(n)
代码实现：
func judgeSquareSum(_ c: Int) -> Bool {
if c == 0 { return true }
var set = Set<Int>()
for i in 0...Int(sqrt(Double(c))) {
set.insert(i*i)
if set.contains(c-i*i) {
return true
}
}
return false
}
【思路3】
1、双指针
2、定义两个变量left=0 right=sqrt(c)
3、两个变量的平方和小于c，那么左指针+1
4、两个变量的平方和大于c，那么右指针-1，直到遍历结束
5、 时间复杂度O(n)
6、空间复杂度O(1)
代码实现：
func judgeSquareSum(_ c: Int) -> Bool {
if c == 0 { return true }
var j = Int.init(sqrt(Double(c)))
var i = 0
while i < j {
if i*i + j*j < c {
i+=1
}
if i*i + j*j > c {
j-=1
}
if i*i + j*j == c {
return true
}
}
return false
}
