算法思想:
- 双指针枚举i,j;类似三数之和
class Solution {
public:bool judgeSquareSum(int c) {long long sum=0;vector<int> dp;dp.push_back(0);long long start=1;while(sum < c){sum = start *start;if(sum>c) break;else dp.push_back(sum);start++;}long long l=0,r=dp.size()-1;while(l<=r){//long long tmp =dp[l] + dp[r]; 会溢出if(dp[l] < c-dp[r]){l++;continue;}else if (dp[l] > c - dp[r]){r--;continue;}else if(dp[l] == c-dp[r]) return true;}return false;}
};
但注意一点,dp[l] + dp[r]会溢出,所以用减法不会溢出;