LeetCode 每日一题 633. 平方数之和

[633. 平方数之和](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/)

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

题目描述：判断一个非负整数是否为两个整数的平方和。

可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。

本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。

代码:

class Solution {
public:
    bool judgeSquareSum(int c) {
        bool res = false;
        long long sqrtc = sqrt(c);
        for (long long i = 0, j = sqrtc; i <= sqrtc; i++)
        {
            while(j >= i && i * i + j * j > c) j--;
            // cout << i << ' ' << j << endl;
            if (i * i + j * j == c) res = true;
        }
        return res;
    }
};

代码模板

双指针:

for (int i = 0, j = n; i < n; i ++)
{
    while (j > i && check(i, j)) j --;

    // 具体问题的逻辑
}
常见问题分类
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作