題意：給你一個(gè)非負(fù)數(shù)c，判斷該數(shù)是不是兩個(gè)完全平方數(shù)的和（a^2 + b^2） = c.
解題思路：
思路一：暴力肺缕。篩選a榕茧，b：a^2 <= c, b ^2 <= c，然后組合a^2 + b^2與c比較懂牧，時(shí)間復(fù)雜度O(sqrt(c)*sqrt(c) = O(c)，會(huì)TLE.
思路二：使用sqrt函數(shù)或自己寫(xiě)二分查找尊勿。先篩選a需滿足a^2 <= c僧凤，再判斷c-a^2 是否為完全平方數(shù)，令b = (c-a^2)元扔，判斷sqrt(b) == int( sqrt(b) ) ?
時(shí)間復(fù)雜度：O(sqrt(c) * log(c)),找a需要O(sqrt(c))躯保，判斷b的sqrt函數(shù)需要O(log=(c))。查看ac detail時(shí)發(fā)現(xiàn)運(yùn)行時(shí)間為12ms澎语，還算可以接受途事。
空間復(fù)雜度：O(log(c)),sqrt函數(shù)需要logc空間验懊。
class Solution {
public:
bool judgeSquareSum(int c) {
for(long long a = 0; a * a <= c; a++) //使用long long 防止溢出
{
double b = sqrt(c - a * a);
if(b == int(b) )
return true;
}
return false;
}
};
思路三：使用hashmap，將所有小于c的完全平方數(shù)存為hashmap的鍵尸变，對(duì)應(yīng)的n存為值鲁森，因?yàn)樵趆ashmap中尋找鍵時(shí)間復(fù)雜度是O(1)。
時(shí)間復(fù)雜度：O(sqrt(c))振惰，但是查看ac detail的時(shí)候發(fā)現(xiàn)運(yùn)行時(shí)間為249ms歌溉，是最慢ac程序。
空間復(fù)雜度：因?yàn)殚_(kāi)始的時(shí)候編譯器會(huì)自動(dòng)為hashmap分配一部分內(nèi)存骑晶，當(dāng)hashmap內(nèi)存不夠的時(shí)候痛垛，編譯器會(huì)進(jìn)行hashmap的內(nèi)存擴(kuò)充resize，所以大體也可以將空間復(fù)雜度看做O(c).
class Solution {
public:
bool judgeSquareSum(int c) {
map<long long, int> m;
for(long long a = 0; a * a <= c; a++) //使用long long防止溢出
{
m[a * a] = a; //一邊添加鍵值對(duì)
if(m.find(c - a * a) != m.end()) //一邊查找更快
return true;
}
return false;
}
};
