【双指针】【数之和】 LeetCode 633.平方数之和
算法思想：
- 双指针枚举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]会溢出，所以用减法不会溢出；