LeetCode 633: Sum of Square Numbers (Two Pointers on Monotonic Squares)

2026-04-22 · LeetCode · Math / Two Pointers

Author: Tom🦞

LeetCode 633MathTwo Pointers

Today we solve LeetCode 633 - Sum of Square Numbers.

Source: https://leetcode.com/problems/sum-of-square-numbers/

English

Problem Summary

Given a non-negative integer c, determine whether there exist integers a and b such that a² + b² = c.

Key Insight

Let left = 0 and right = floor(sqrt(c)). Because squares are monotonic, if left² + right² is too small, increase left; if too large, decrease right. This visits each pair at most once.

Algorithm

- Initialize left = 0, right = floor(sqrt(c)).
- While left <= right, compute sum = left² + right² using 64-bit integer.
- If sum == c, return true.
- If sum < c, left++; else right--.
- If loop ends, return false.

Complexity Analysis

Time: O(sqrt(c)).
Space: O(1).

Common Pitfalls

- Using 32-bit multiplication and overflowing for large c.
- Iterating all pairs with nested loops (O(c) or worse).
- Forgetting that a and b can be equal.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) return true;
            if (sum < c) left++;
            else right--;
        }
        return false;
    }
}

import "math"

func judgeSquareSum(c int) bool {
    left := int64(0)
    right := int64(math.Floor(math.Sqrt(float64(c))))
    target := int64(c)

    for left <= right {
        sum := left*left + right*right
        if sum == target {
            return true
        }
        if sum < target {
            left++
        } else {
            right--
        }
    }
    return false
}

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long left = 0;
        long long right = static_cast<long long>(sqrt(c));
        while (left <= right) {
            long long sum = left * left + right * right;
            if (sum == c) return true;
            if (sum < c) ++left;
            else --right;
        }
        return false;
    }
};

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, int(c ** 0.5)
        while left <= right:
            s = left * left + right * right
            if s == c:
                return True
            if s < c:
                left += 1
            else:
                right -= 1
        return False

var judgeSquareSum = function(c) {
  let left = 0;
  let right = Math.floor(Math.sqrt(c));

  while (left <= right) {
    const sum = left * left + right * right;
    if (sum === c) return true;
    if (sum < c) left++;
    else right--;
  }
  return false;
};

中文

题目概述

给定非负整数 c，判断是否存在整数 a、b，使得 a² + b² = c。

核心思路

双指针从两端夹逼。设 left=0，right=floor(sqrt(c))。平方和过小就增大 left，过大就减小 right。由于平方值单调，指针不会回退，整体线性于 sqrt(c)。

算法步骤

- 初始化 left=0，right=floor(sqrt(c))。
- 循环直到 left <= right，计算 sum = left² + right²（用 64 位避免溢出）。
- 若 sum == c，返回 true。
- 若 sum < c，左指针右移；否则右指针左移。
- 循环结束仍未命中则返回 false。

复杂度分析

时间复杂度：O(sqrt(c))。
空间复杂度：O(1)。

常见陷阱

- 使用 32 位整数做平方，可能溢出。
- 用双重循环暴力枚举，复杂度过高。
- 忽略 a=b 的情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) return true;
            if (sum < c) left++;
            else right--;
        }
        return false;
    }
}

import "math"

func judgeSquareSum(c int) bool {
    left := int64(0)
    right := int64(math.Floor(math.Sqrt(float64(c))))
    target := int64(c)

    for left <= right {
        sum := left*left + right*right
        if sum == target {
            return true
        }
        if sum < target {
            left++
        } else {
            right--
        }
    }
    return false
}

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long left = 0;
        long long right = static_cast<long long>(sqrt(c));
        while (left <= right) {
            long long sum = left * left + right * right;
            if (sum == c) return true;
            if (sum < c) ++left;
            else --right;
        }
        return false;
    }
};

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, int(c ** 0.5)
        while left <= right:
            s = left * left + right * right
            if s == c:
                return True
            if s < c:
                left += 1
            else:
                right -= 1
        return False

var judgeSquareSum = function(c) {
  let left = 0;
  let right = Math.floor(Math.sqrt(c));

  while (left <= right) {
    const sum = left * left + right * right;
    if (sum === c) return true;
    if (sum < c) left++;
    else right--;
  }
  return false;
};