LeetCode演算法題-Sum of Square Numbers（Java實現）
這是悅樂書的第276 次更新，第292 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第144題（順位題號是633）。給定一個非負整數c，判斷是否存在兩個整數a和b，使得a的平方與b的平方之和等於c。例如：
輸入：5
輸出：true
說明：1 x 1 + 2 x 2 = 5
輸入：3
輸出：false
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
暴力解法，直接使用兩層for迴圈，分別從0開始，上限為c的平方根，如果存在兩數平方和等於c，就返回true，否則返回false。
此解法可能會超時，不建議使用。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
for (int a=0; a <= num; a++) {
for (int b=0; b<= num; b++) {
if (a*a + b*b == c) {
return true;
}
}
}
return false;
}
03 第二種解法
使用HashSet。如果在c的平方根範圍內，存在兩數平方和等於c，那麼先將單個數的平方值a新增進set中，然後再去判斷set中是否存在c減去a的另一個值b，如果存在就返回true。
public boolean judgeSquareSum(int c) {
HashSet<Integer> set = new HashSet<>();
int num = (int)Math.sqrt(c);
for (int i=num; i >= 0; i--) {
set.add(i*i);
if (set.contains(c-i*i)) {
return true;
}
}
return false;
}
04 第三種解法
我們也可以不使用HashSet。依舊是先確定取值範圍，上限為c的平方根取整。在0到c的平方根範圍內，如果當前一個數的平方根正好等於c，直接返回true，因為另外一個數可能是0；如果不等於，就用c減去當前此數的平方根並賦值給a，再對得到的差開方並賦值給b，如果b的平方等於a，直接返回true，說明存在兩數之和等於c。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
for (int i=num; i >= 0; i--) {
if (i*i == c) {
return true;
}
int a = c - i*i;
int b = (int)Math.sqrt(a);
if (b*b == a) {
return true;
}
}
return false;
}
05 第四種解法
使用雙指標。首指標a從0開始，尾指標b從c的平方根開始，如果a的平方加上b的平方的值大於c，那麼尾指標b就減1；如果小於c，那麼首指標a就加1；如果等於c，直接返回true。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
int a = 0;
int b = num;
while (a <= b) {
if (a*a + b*b > c) {
b--;
} else if (a*a + b*b < c) {
a++;
} else {
return true;
}
}
return false;
}
06 小結
此題本質上是一道數學題，先需要確定取值範圍，然後在該範圍內找到合適的兩個數，使其平方和等於另外一個數，你可以使用二分查詢法、雙指標或者其他演算法來實現。
演算法專題目前已日更超過四個月 ，演算法題文章144 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！