题目

image.png

思路：双指针

  • 双指针，一根left指向0，一根right指向sqrt(c)
  • 如果cur_sum == c，返回true
  • 如果cur_sum < c，说明应该变大，那么left += 1

  • 如果cur_sum > c，说明应该缩小，那么right -= 1

    代码：

    1. class Solution {
    2. public:
    3.   bool judgeSquareSum(int c) {
    4.       long long left = 0, right = sqrt(c);
    5.       while (left <= right) {
    6.           long long cur_sum = left * left + right * right;
    7.           if (cur_sum == c) {
    8.               return true;
    9.           } else if (cur_sum < c) {
    10.               left += 1;
    11.           } else if (cur_sum > c) {
    12.               right -= 1;
    13.           }
    14.       }
    16.       return false;
    17.   }
    18. };

    为什么双指针不会漏解？ https://leetcode-cn.com/problems/sum-of-square-numbers/solution/shuang-zhi-zhen-de-ben-zhi-er-wei-ju-zhe-ebn3/