2022416Leetcode633.平方数之和

第一版&＃xff0c;使用双指针&＃xff0c;但是造成了溢出。

class Solution {
public:bool judgeSquareSum(int c) {vector<int> arr(c&＃43;1);for(int i &＃61; 0;i < c&＃43;1;i&＃43;&＃43;){arr[i] &＃61; i;}int l &＃61; 0;int r &＃61; c;while(l <&＃61; r){unsigned long long int num &＃61; arr[l] * arr[l] &＃43; arr[r] * arr[r];if(num &＃61;&＃61; c){return true;}else if(num > c){r--;}else {l&＃43;&＃43;;}}return false;}
};


主要是需要使用sqrt 来防止溢出和降低时间复杂度。

第二版&＃xff0c;依然会溢出。
Line 11: Char 43: runtime error: signed integer overflow: 829921 &＃43; 2146654224 cannot be represented in type ‘int’ (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:20:43

class Solution {
public:bool judgeSquareSum(int c) {int a &＃61; sqrt(c);vector<int> arr(a&＃43;1);for(int i &＃61; 0;i < arr.size();i&＃43;&＃43;){arr[i] &＃61; i;}int l &＃61; 0,r &＃61; a;while(l <&＃61; r){long long num &＃61; arr[l]*arr[l] &＃43; arr[r]*arr[r];if(num &＃61;&＃61; c){return true;}else if(num > c){r--;}else{l&＃43;&＃43;;}}return false;}
};


第三版&＃xff0c;将数组换成了long

class Solution {
public:bool judgeSquareSum(int c) {long a &＃61; sqrt(c);vector<long> arr(a&＃43;1);for(int i &＃61; 0;i < arr.size();i&＃43;&＃43;){arr[i] &＃61; i;}int l &＃61; 0,r &＃61; a;while(l <&＃61; r){long long num &＃61; arr[l]*arr[l] &＃43; arr[r]*arr[r];if(num &＃61;&＃61; c){return true;}else if(num > c){r--;}else{l&＃43;&＃43;;}}return false;}
};


看了下官方答案&＃xff0c;发现没有必要使用数组

class Solution {
public:bool judgeSquareSum(int c) {long left &＃61; 0;long right &＃61; (int)sqrt(c);while (left <&＃61; right) {long sum &＃61; left * left &＃43; right * right;if (sum &＃61;&＃61; c) {return true;} else if (sum > c) {right--;} else {left&＃43;&＃43;;}}return false;}
};作者&＃xff1a;LeetCode-Solution
链接&＃xff1a;https://leetcode-cn.com/problems/sum-of-square-numbers/solution/ping-fang-shu-zhi-he-by-leetcode-solutio-8ydl/
来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
著作权归作者所有。商业转载请联系作者获得授权&＃xff0c;非商业转载请注明出处。