无边界条件下正负整数平方根查找算法的优雅实现问询

嘿，这个问题挺有意思的！我之前准备算法面试的时候也琢磨过类似场景，给你分享几个不依赖「负负得正」这个数学结论的实现思路，逻辑上更直白，也更贴合平方根的定义：

1. 先找正根，直接生成负根（最直观的优雅实现） #

这个思路完全绕开乘法符号规则，核心就是基于平方根的定义：如果x是n的正平方根，那么-x必然是它的负平方根。我们只需要先找到正的整数平方根，再直接取相反数得到负根即可，不需要推导“负数相乘得正”。

示例代码（Python）：

def find_integer_square_roots(n):
    # 实数范围内负数无整数平方根，可根据需求调整逻辑
    if n < 0:
        return []
    
    # 用你熟悉的递增查找找正根，也可以换成二分优化
    positive_root = 0
    while (positive_root + 1) ** 2 <= n:
        positive_root += 1
    
    # 验证是否为精确平方根（若允许近似根可跳过此步）
    if positive_root ** 2 != n:
        return []
    
    # 直接基于正根生成结果，无需依赖负负得正
    if n == 0:
        return [0]
    return [positive_root, -positive_root]

2. 双向遍历验证（完全无推导的 brute force 实现） #

如果想彻底摆脱任何数学推导，甚至连“正根取反得负根”都不想用，可以直接从0开始，同时向正负两个方向遍历候选数，逐个验证平方是否等于目标值。

示例代码（Python）：

def find_integer_square_roots(n):
    roots = []
    if n < 0:
        return roots
    
    # 先检查0的情况
    if 0 ** 2 == n:
        roots.append(0)
    
    candidate = 1
    while True:
        current_square = candidate ** 2
        if current_square > n:
            break
        if current_square == n:
            roots.append(candidate)
            roots.append(-candidate)
        candidate += 1
    
    return roots

这个思路非常直白：就是把每个正整数和对应的负整数都拿出来验证，符合条件就加入结果，全程不需要任何数学推导，完全依赖对平方根定义的直接验证。

3. 二分查找优化版（高效且优雅） #

如果需要处理大数，递增查找效率太低的话，可以用二分查找先找到正根，再直接生成负根。这个思路同样不依赖负负得正的原理，只是利用二分法快速缩小查找范围，最后基于平方根定义生成结果。

示例代码（Python）：

def _find_positive_root(n):
    if n < 0:
        return None
    left, right = 0, n
    while left <= right:
        mid = (left + right) // 2
        square = mid ** 2
        if square == n:
            return mid
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1
    return None  # 无精确整数平方根时返回None

def find_integer_square_roots(n):
    positive_root = _find_positive_root(n)
    if positive_root is None:
        return []
    if positive_root == 0:
        return [0]
    return [positive_root, -positive_root]

二分查找的时间复杂度是O(log n)，比递增查找的O(n)高效得多，同时逻辑上依然保持简洁，完全不需要依赖乘法符号规则。

内容的提问来源于stack exchange，提问作者edmamerto