633. 平方数之和 Sum of Square Numbers

【题目描述】
给定一个非负整数 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
}

后续会继续更新文章，也可以关注我的公众号，基本每日一题🙂：

个人公号.jpg