看到这类题目很多人的第一反应是掏出IDE准备暴力循环但真正动手之后会发现两个问题一是循环上界设多少完全没谱二是就算跑出结果也不敢保证唯一。这道“整数加100和加168都是完全平方数”的经典题其实藏着非常漂亮的数学结构用Java实现时也有不少值得讲的细节。这篇文章我会从题目拆解开始给出三种可落地的Java解法再把判断完全平方数时容易踩的浮点精度坑、溢出坑都摊开讲清楚。1. 先把题目拆透这道题到底在问什么1.1 变量与条件的数学翻译题目原文是一个整数它加上100后是一个完全平方数加上168又是一个完全平方数请问该数是多少先别急着写代码把自然语言翻译成数学语言。设这个整数为 x那么存在两个整数 m 和 n使得x 100 m²x 168 n²这里有一个很关键的顺序问题两个条件是“分别加上100和168”不是“加上100之后再在结果上加上168”。如果你把第二个条件理解成 x 100 168 n²那整道题的答案会完全不一样后面我会专门讲这个表述陷阱。既然是同一个 x那么两个式子相减是最自然的操作(x 168) - (x 100) n² - m²化简后就是n² - m² 68到这里题目已经从“找一个整数 x”转化成了“找两个整数 m、n使它们的平方差等于68”然后 x m² - 100 自然就出来了。这一步转化是整个题目的灵魂也是面试官最想看到的思维过程。1.2 为什么“68”这么关键68这个数字不是随便来的它就是两个条件之间的差的绝对值。168 - 100 68就这么简单。但恰恰是这个差值决定了题目的解法和解的个数。平方差公式告诉我们n² - m² (n - m)(n m)所以问题又变成了把68拆成两个整数相乘并且这两个因数恰好等于 n - m 和 n m。这就把一个看似无限的枚举问题变成了一个有限范围内的因数分解问题。68的因数对不多也就几组手算都能算出来编程做更是秒杀。1.3 先别急着写代码手推一遍答案在打开编辑器之前我建议你先拿纸笔推一遍。这个过程会让你对解法有真正的理解而不是背代码。68的因数对包括1 × 682 × 344 × 17注意n - m 和 n m 必须同奇偶因为它们的和是 2n一定是偶数它们的差是 2m也一定是偶数。所以如果两个因数一个是奇数一个是偶数直接排除。看一遍1 和 68一奇一偶排除。2 和 34两个都是偶数可行。于是 n - m 2n m 34解得 n 18m 16。4 和 17一奇一偶排除。所以 m 16n 18代回 x m² - 100 256 - 100 156。验证一下156 100 256 16²156 168 324 18²。答案完美。注意这里用“因数对同奇偶”筛选有一个前提就是 m、n 我们默认取非负整数。实际上 m 和 n 取负数也不影响平方结果但因为平方值只看绝对值最终得到的 x 不变。这个细节在面试中主动提出来会显得你考虑问题很全面。2. Java解法一暴力枚举简单但够用2.1 思路与边界确定最直白的思路是把 x 的可能取值一个个试过去每个 x 都检查 x 100 和 x 168 是不是完全平方数。问题来了x 的枚举范围怎么定下界很明确因为 x 168 必须是非负数完全平方数最小是0所以 x ≥ -168。上界呢这是暴力法最尴尬的地方。题目没有限制 x 的范围理论上它可以非常大。但因为 n² - m² 68如果 n m那么 n - m ≥ 1整数之间最小差1于是n² - m² (n - m)(n m) ≥ 1 × (2m 1) 2m 1也就是说 2m 1 ≤ 68解得 m ≤ 33。这其实告诉我们就算用暴力法也没必要把 x 枚举到天上去。x m² - 100m 最大33所以 x 最大不超过 33² - 100 989。看到没有上界其实小得惊人。当然如果你不想在暴力法里做这个推导也可以拍脑袋给一个比较大的上界比如十万、一百万。但知道了数学关系之后你会更安心枚举到 1000 以内就够了。2.2 基础版代码实现直接上代码public class BruteForceSolution { public static void main(String[] args) { int count 0; // 根据 m 33 可知 x 最大为 33*33 - 100 989 for (int x -168; x 1000; x) { if (isPerfectSquare(x 100) isPerfectSquare(x 168)) { System.out.println(找到整数: x); count; } } System.out.println(共找到 count 个); } private static boolean isPerfectSquare(int num) { if (num 0) { return false; } int sqrt (int) Math.sqrt(num); return sqrt * sqrt num; } }isPerfectSquare的写法是这套代码的核心先用Math.sqrt开方再强转成 int 截断小数部分最后用乘法回验。比如 num 256sqrt 16.0转 int 还是1616×16 256相等返回 true。比如 num 257sqrt ≈ 16.03转 int 变成1616×16 256 ≠ 257返回 false。输出结果找到整数: 156 共找到 1 个这个版本代码量最小逻辑直白特别适合第一次接触这道题的人。2.3 这版代码的坑Math.sqrt的浮点隐患暴力解法看着简单但Math.sqrt返回的是 double这里藏着几个细节。第一个坑用Math.sqrt(num)后强转 int如果 num 本身是负数Math.sqrt会返回 NaN强转成 int 的结果在 Java 里是 0。所以isPerfectSquare里必须先做if (num 0)的防御判断否则你的逻辑会出错。我见过有人写出(int)Math.sqrt(-1) 0然后 0×0 0误判 -1 是完全平方数这就是典型的防御性编程没做到位。第二个坑double 的精度问题。当 num 非常大时Math.sqrt的结果可能是一个很接近整数的浮点数比如 999999.9999999强转 int 后变成 999999回验就可能不相等。更稳妥的做法是判断double s Math.sqrt(num); if (s - Math.floor(s) 1e-10) { // 认为是完全平方数 }但我不推荐这个写法因为误差阈值难定不同数量级下表现不稳定。最可靠的永远是“整数回验”方案转成 int 后乘回来再比较原数。只要 num 不超过 int 范围这个方案就是精确的。第三个坑乘法溢出。sqrt * sqrt如果 num 接近 Integer.MAX_VALUEsqrt 约等于 4634046340 × 46340 2147395600没溢出。但如果 num 超过 int 范围或者你把判断逻辑用在了 long 类型上就可能悄悄溢出变成负数导致判断结果完全错误。下面一节会专门讲大数场景。3. Java解法二因数分解一步到位3.1 从平方差公式到因数对暴力法适合理解题目但如果你想在面试里展示出数学功底因数分解法才是真正的标准答案。前面已经推过n² - m² (n - m)(n m) 68。设 a n - mb n m那么 a × b 68并且有 b a 0因为 m、n 非负且 n m这里先讨论正数情况。同时a 和 b 必须同奇偶。理由很简单a b 2n是偶数所以 a、b 要么都是偶数要么都是奇数。而 a × b 68 是偶数排除了“两个奇数相乘”的可能所以 a 和 b 必须都是偶数。这就是一个非常规整的逻辑链枚举 68 的所有正因数对。过滤掉不同奇偶的组合。过滤掉 a b 的组合因为 n - m n m。解出 n (a b) / 2m (b - a) / 2。代回 x m² - 100。3.2 奇偶性筛选的数学理由这一步值得单独说一下。为什么网上很多答案里看到 68 2 × 34 就直接跳过了 1 × 68 和 4 × 17有人说是“因为 68 的因数里只有 2 和 34 都是偶数”这其实只是结果不是原因。真正的原因就是我上面写的同奇偶判断。把它讲明白你会比那些“背答案”的人强很多如果 a、b 一奇一偶那么 a b 是奇数但 a b 2n 必须是偶数矛盾。如果 a、b 都是奇数那么 a × b 是奇数但 a × b 68 是偶数矛盾。所以 a、b 只能都是偶数。有了这层推导你甚至可以给出一个一般性结论当目标差值 D 为偶数时如果 D 不是 4 的倍数那么 D 无法分解成两个偶数的乘积平方差为 D 的整数对就不存在。比如 D 2只能拆成 1×2一奇一偶无解。这个扩展思路在后面讲通用解法时非常有用。3.3 Java实现枚举因数并筛选我把因数分解法的完整代码写出来public class FactorizationSolution { public static void main(String[] args) { int diff 168 - 100; // 68 for (int a 1; a * a diff; a) { if (diff % a ! 0) { continue; } int b diff / a; // 要求 b a且 a、b 同奇偶 if (b a) { continue; } if ((a 1) ! (b 1)) { continue; } int m (b - a) / 2; int n (a b) / 2; int x m * m - 100; System.out.println(a a , b b , m m , n n , x x); // 验证 int s1 m * m; int s2 n * n; if (s1 x 100 s2 x 168) { System.out.println(验证通过); } } } }这段代码里有个小技巧循环条件a * a diff意味着 a 只需要枚举到 sqrt(diff) 就够了因为如果 a 是较小因数b diff / a 自动就是较大因数。你不需要枚举到 68只要 a 从1试到8因为 8 × 8 64 ≤ 68四组因数对都能覆盖到。运行输出a2, b34, m16, n18, x156 验证通过代码只输出一组结果数学上也是唯一解跟手推完全一致。3.4 一个重要扩展一个数加上100是平方数再加上168也是平方数我前面提醒过表述陷阱现在用因数分解法来展示这个陷阱的威力。如果题目改成“一个整数它加上100后是一个完全平方数再加上168又是一个完全平方数”那条件就变成x 100 m²x 100 168 n²两个式子相减得到n² - m² 168而不是 68。用同样的因数分解代码把 diff 改成168168的因数对a b有1 × 168一奇一偶排除。2 × 84两个偶数可行m 41n 43x 41² - 100 1581。3 × 56一奇一偶排除。4 × 42两个偶数可行m 19n 23x 19² - 100 261。6 × 28两个偶数可行m 11n 17x 21。7 × 24一奇一偶排除。8 × 21一奇一偶排除。12 × 14两个偶数可行m 1n 13x -99。所以这个“改版”题目有四个答案-99、21、261、1581。你看仅仅是把“加上168”换成“再加上168”差值就从68变成168解的个数也从1个变成4个。这就是为什么读题时一字之差写代码前务必把数学关系确认清楚。以后不管遇到哪个版本用因数分解法都能快速解出还不会漏解。4. Java解法三倒推双循环更通用的视角4.1 思路换个角度枚举暴力法是枚举 x因数分解法是拆因数还有第三种思路直接枚举 m然后用 n² m² 68 去判断。为什么要枚举 m因为 m 是平方根它的取值范围比 x 小得多。根据之前的推导n m 时n² - m² (n - m)(n m)由于 n - m ≥ 1n m ≥ 2m 1所以68 ≥ 2m 1m 最大只能取到 33。也就是说只需要从 0 到 33 枚举 m34次判断就能解决问题。4.2 代码实现与复杂度分析代码长这样public class EnumerateRootSolution { public static void main(String[] args) { int diff 168 - 100; for (int m 0; m 33; m) { long m2 (long) m * m; // 避免 int 乘法溢出 long n2 m2 diff; long n (long) Math.sqrt(n2); if (n * n n2) { long x m2 - 100; System.out.println(m m , n n , x x); } } } }我来解释几个细节(long) m * m这一步很关键。如果 m 是 intm * m 先按 int 计算一旦超过 2^31 - 1 就会溢出结果变成负数。虽然这里 m 最大33不会溢出但培养这种防御习惯很重要尤其是日后处理大数题目。Math.sqrt(n2)的参数是 long会自动转成 double。如果 n2 很大double 精度只有约 15 位十进制有效数字可能出现判断偏差。不过这道题的 n2 最大不超过 33² 68 1157完全在安全范围内。循环上限直接写死成33是因为前面推导已经证明 m ≤ 33。如果你把 diff 换成其他值上限也要重新推导不能照抄。输出结果不变仍然是 x 156。4.3 三种解法对比用表格直观对比一下解法枚举对象循环次数时间复杂度优点缺点暴力枚举x约1170次O(N)思路直接最贴合题目字面需要事先确定范围否则容易瞎猜上界因数分解68的因数不到10次O(√D)数学思路最漂亮不遗漏解需要掌握同奇偶筛选逻辑倒推枚举m34次O(√D)代码短判断逻辑直观需要先推导 m 的上界三种方法各有定位新手先写暴力法理解题意面试时写因数分解法展示思维层次工程上做通用工具时用倒推枚举法最不容易出错。提示如果你要把解法做成一个通用的“平方差等于 D 的整数对查找器”因数分解法是最稳的因为它的循环次数只跟 D 的因数个数有关并且天然不会漏解。5. 实战中的坑与常见问题速查5.1 完全平方数判断的精度问题这是我在实际代码评审里看到最多的问题。很多人写判断正方形是这样写的double sqrt Math.sqrt(num); if (sqrt (int) sqrt) { return true; }这段代码在小整数范围内能用但有两个隐患(int) sqrt是把 double 强转成 int如果 sqrt 非常接近一个整数但比整数小一点点强转会得到比实际整数小1的数导致误判。double 在表达极大整数时精度不足。当 num 超过 2^53 时甚至 num 本身转成 double 就会丢精度。稳妥写法我之前已经给过先算 int sqrt (int) Math.sqrt(num)再判断 sqrt * sqrt num。或者干脆用 BigDecimal 做完全限定判断不过那道题用不上。5.2 整数溢出风险这道题的中间变量虽然不大但稍微改版就可能撞上溢出。比如改成“加上1000000后是平方数加上2000000后也是平方数”m 和 x 都会大不少int 乘法很容易出问题。我的习惯是所有可能先乘后判的中间量都声明成 long。Java 里 long 的范围比 int 大太多在小题目里基本等于“免费保险”。如果真的遇到更大范围那就要考虑用java.math.BigInteger了不过那是另一个场景的事。5.3 负数范围与零的处理很多初学者忽略 x 可以是负数。这道题里 x -168 就是一个边界值因为 x 168 0 0²但 x 100 -68不是平方数。把所有边界情况都考虑一遍才算完整解题。还有 m、n 取负数的问题。m -16 时m² 同样是256不影响 x。所以因数分解法里我默认 m、n 取非负整数最终 x 的结果不变。如果你想跟面试官讨论这个点可以主动提一句因为平方的符号不影响结果所以非负解已经覆盖所有情况。5.4 面试里怎么答才算加分这道题在很多面试里不是笔试题而是口述题。面试官可能一边喝茶一边问你这个数是多少我建议的回答节奏是先说出数学关系设 x 100 m²x 168 n²。然后相减得到 n² - m² 68。接着因式分解68 2 × 34所以 n - m 2n m 34。解出 n 18m 16x 156。最后验证156 100 256156 168 324。整个过程大概一分钟不用写一行代码。如果你一上来就说“我循环跑一下”面试官心里的评分至少降一档。这道题考察的核心不是你会不会用 Java而是你有没有把问题数学化的意识。6. 个人经验与扩展建议这道题我几乎每年都会用不同的语言重写一遍每次都会有新的感受。最早我写 Python 版本的时候用的就是暴力循环上界拍脑袋写了十万结果跑完还怀疑是不是漏了解。后来做了数学推导才发现上界一千都不到。那种“豁然开朗”的感觉让我养成了一个习惯拿到算法题先别碰键盘用纸笔把约束条件理清楚尤其是变量之间的数量关系。如果你打算把这类题整理成一套通用工具可以沿这个方向扩展输入一个差值 D 和基准偏移量 offset输出所有满足 (x offset) 与 (x offset D) 均为完全平方数的整数 x。核心思路就是因数分解 同奇偶筛选。我之前写过一个这样的方法核心代码只有十几行却能处理一整个系列的“平方差”题目效果很香。另外我想把这道题再往深处挖一点当你把 D 固定后x 的解其实很有限因为 n - m ≥ 1 决定了 m 是有限集。遇到这类“两条件都是平方数”的问题都可以先转换成平方差再用因数分解收束范围。这个方法不局限于 JavaC、Python、JavaScript 都适用。最后再分享一个小经验写完代码后不要只看输出结果就收工。手动把等式代回去验证一遍是成本最低的防错手段。我见过有同学因为 m、n 的符号问题答案输出了一堆重复项就是因为缺了最后的数学验证。这道题里的 156 虽然简单但验证步骤传递的习惯在以后处理更复杂的数学编程题时价值会成倍放大。
看到这类题目很多人的第一反应是掏出IDE准备暴力循环但真正动手之后会发现两个问题一是循环上界设多少完全没谱二是就算跑出结果也不敢保证唯一。这道“整数加100和加168都是完全平方数”的经典题其实藏着非常漂亮的数学结构用Java实现时也有不少值得讲的细节。这篇文章我会从题目拆解开始给出三种可落地的Java解法再把判断完全平方数时容易踩的浮点精度坑、溢出坑都摊开讲清楚。1. 先把题目拆透这道题到底在问什么1.1 变量与条件的数学翻译题目原文是一个整数它加上100后是一个完全平方数加上168又是一个完全平方数请问该数是多少先别急着写代码把自然语言翻译成数学语言。设这个整数为 x那么存在两个整数 m 和 n使得x 100 m²x 168 n²这里有一个很关键的顺序问题两个条件是“分别加上100和168”不是“加上100之后再在结果上加上168”。如果你把第二个条件理解成 x 100 168 n²那整道题的答案会完全不一样后面我会专门讲这个表述陷阱。既然是同一个 x那么两个式子相减是最自然的操作(x 168) - (x 100) n² - m²化简后就是n² - m² 68到这里题目已经从“找一个整数 x”转化成了“找两个整数 m、n使它们的平方差等于68”然后 x m² - 100 自然就出来了。这一步转化是整个题目的灵魂也是面试官最想看到的思维过程。1.2 为什么“68”这么关键68这个数字不是随便来的它就是两个条件之间的差的绝对值。168 - 100 68就这么简单。但恰恰是这个差值决定了题目的解法和解的个数。平方差公式告诉我们n² - m² (n - m)(n m)所以问题又变成了把68拆成两个整数相乘并且这两个因数恰好等于 n - m 和 n m。这就把一个看似无限的枚举问题变成了一个有限范围内的因数分解问题。68的因数对不多也就几组手算都能算出来编程做更是秒杀。1.3 先别急着写代码手推一遍答案在打开编辑器之前我建议你先拿纸笔推一遍。这个过程会让你对解法有真正的理解而不是背代码。68的因数对包括1 × 682 × 344 × 17注意n - m 和 n m 必须同奇偶因为它们的和是 2n一定是偶数它们的差是 2m也一定是偶数。所以如果两个因数一个是奇数一个是偶数直接排除。看一遍1 和 68一奇一偶排除。2 和 34两个都是偶数可行。于是 n - m 2n m 34解得 n 18m 16。4 和 17一奇一偶排除。所以 m 16n 18代回 x m² - 100 256 - 100 156。验证一下156 100 256 16²156 168 324 18²。答案完美。注意这里用“因数对同奇偶”筛选有一个前提就是 m、n 我们默认取非负整数。实际上 m 和 n 取负数也不影响平方结果但因为平方值只看绝对值最终得到的 x 不变。这个细节在面试中主动提出来会显得你考虑问题很全面。2. Java解法一暴力枚举简单但够用2.1 思路与边界确定最直白的思路是把 x 的可能取值一个个试过去每个 x 都检查 x 100 和 x 168 是不是完全平方数。问题来了x 的枚举范围怎么定下界很明确因为 x 168 必须是非负数完全平方数最小是0所以 x ≥ -168。上界呢这是暴力法最尴尬的地方。题目没有限制 x 的范围理论上它可以非常大。但因为 n² - m² 68如果 n m那么 n - m ≥ 1整数之间最小差1于是n² - m² (n - m)(n m) ≥ 1 × (2m 1) 2m 1也就是说 2m 1 ≤ 68解得 m ≤ 33。这其实告诉我们就算用暴力法也没必要把 x 枚举到天上去。x m² - 100m 最大33所以 x 最大不超过 33² - 100 989。看到没有上界其实小得惊人。当然如果你不想在暴力法里做这个推导也可以拍脑袋给一个比较大的上界比如十万、一百万。但知道了数学关系之后你会更安心枚举到 1000 以内就够了。2.2 基础版代码实现直接上代码public class BruteForceSolution { public static void main(String[] args) { int count 0; // 根据 m 33 可知 x 最大为 33*33 - 100 989 for (int x -168; x 1000; x) { if (isPerfectSquare(x 100) isPerfectSquare(x 168)) { System.out.println(找到整数: x); count; } } System.out.println(共找到 count 个); } private static boolean isPerfectSquare(int num) { if (num 0) { return false; } int sqrt (int) Math.sqrt(num); return sqrt * sqrt num; } }isPerfectSquare的写法是这套代码的核心先用Math.sqrt开方再强转成 int 截断小数部分最后用乘法回验。比如 num 256sqrt 16.0转 int 还是1616×16 256相等返回 true。比如 num 257sqrt ≈ 16.03转 int 变成1616×16 256 ≠ 257返回 false。输出结果找到整数: 156 共找到 1 个这个版本代码量最小逻辑直白特别适合第一次接触这道题的人。2.3 这版代码的坑Math.sqrt的浮点隐患暴力解法看着简单但Math.sqrt返回的是 double这里藏着几个细节。第一个坑用Math.sqrt(num)后强转 int如果 num 本身是负数Math.sqrt会返回 NaN强转成 int 的结果在 Java 里是 0。所以isPerfectSquare里必须先做if (num 0)的防御判断否则你的逻辑会出错。我见过有人写出(int)Math.sqrt(-1) 0然后 0×0 0误判 -1 是完全平方数这就是典型的防御性编程没做到位。第二个坑double 的精度问题。当 num 非常大时Math.sqrt的结果可能是一个很接近整数的浮点数比如 999999.9999999强转 int 后变成 999999回验就可能不相等。更稳妥的做法是判断double s Math.sqrt(num); if (s - Math.floor(s) 1e-10) { // 认为是完全平方数 }但我不推荐这个写法因为误差阈值难定不同数量级下表现不稳定。最可靠的永远是“整数回验”方案转成 int 后乘回来再比较原数。只要 num 不超过 int 范围这个方案就是精确的。第三个坑乘法溢出。sqrt * sqrt如果 num 接近 Integer.MAX_VALUEsqrt 约等于 4634046340 × 46340 2147395600没溢出。但如果 num 超过 int 范围或者你把判断逻辑用在了 long 类型上就可能悄悄溢出变成负数导致判断结果完全错误。下面一节会专门讲大数场景。3. Java解法二因数分解一步到位3.1 从平方差公式到因数对暴力法适合理解题目但如果你想在面试里展示出数学功底因数分解法才是真正的标准答案。前面已经推过n² - m² (n - m)(n m) 68。设 a n - mb n m那么 a × b 68并且有 b a 0因为 m、n 非负且 n m这里先讨论正数情况。同时a 和 b 必须同奇偶。理由很简单a b 2n是偶数所以 a、b 要么都是偶数要么都是奇数。而 a × b 68 是偶数排除了“两个奇数相乘”的可能所以 a 和 b 必须都是偶数。这就是一个非常规整的逻辑链枚举 68 的所有正因数对。过滤掉不同奇偶的组合。过滤掉 a b 的组合因为 n - m n m。解出 n (a b) / 2m (b - a) / 2。代回 x m² - 100。3.2 奇偶性筛选的数学理由这一步值得单独说一下。为什么网上很多答案里看到 68 2 × 34 就直接跳过了 1 × 68 和 4 × 17有人说是“因为 68 的因数里只有 2 和 34 都是偶数”这其实只是结果不是原因。真正的原因就是我上面写的同奇偶判断。把它讲明白你会比那些“背答案”的人强很多如果 a、b 一奇一偶那么 a b 是奇数但 a b 2n 必须是偶数矛盾。如果 a、b 都是奇数那么 a × b 是奇数但 a × b 68 是偶数矛盾。所以 a、b 只能都是偶数。有了这层推导你甚至可以给出一个一般性结论当目标差值 D 为偶数时如果 D 不是 4 的倍数那么 D 无法分解成两个偶数的乘积平方差为 D 的整数对就不存在。比如 D 2只能拆成 1×2一奇一偶无解。这个扩展思路在后面讲通用解法时非常有用。3.3 Java实现枚举因数并筛选我把因数分解法的完整代码写出来public class FactorizationSolution { public static void main(String[] args) { int diff 168 - 100; // 68 for (int a 1; a * a diff; a) { if (diff % a ! 0) { continue; } int b diff / a; // 要求 b a且 a、b 同奇偶 if (b a) { continue; } if ((a 1) ! (b 1)) { continue; } int m (b - a) / 2; int n (a b) / 2; int x m * m - 100; System.out.println(a a , b b , m m , n n , x x); // 验证 int s1 m * m; int s2 n * n; if (s1 x 100 s2 x 168) { System.out.println(验证通过); } } } }这段代码里有个小技巧循环条件a * a diff意味着 a 只需要枚举到 sqrt(diff) 就够了因为如果 a 是较小因数b diff / a 自动就是较大因数。你不需要枚举到 68只要 a 从1试到8因为 8 × 8 64 ≤ 68四组因数对都能覆盖到。运行输出a2, b34, m16, n18, x156 验证通过代码只输出一组结果数学上也是唯一解跟手推完全一致。3.4 一个重要扩展一个数加上100是平方数再加上168也是平方数我前面提醒过表述陷阱现在用因数分解法来展示这个陷阱的威力。如果题目改成“一个整数它加上100后是一个完全平方数再加上168又是一个完全平方数”那条件就变成x 100 m²x 100 168 n²两个式子相减得到n² - m² 168而不是 68。用同样的因数分解代码把 diff 改成168168的因数对a b有1 × 168一奇一偶排除。2 × 84两个偶数可行m 41n 43x 41² - 100 1581。3 × 56一奇一偶排除。4 × 42两个偶数可行m 19n 23x 19² - 100 261。6 × 28两个偶数可行m 11n 17x 21。7 × 24一奇一偶排除。8 × 21一奇一偶排除。12 × 14两个偶数可行m 1n 13x -99。所以这个“改版”题目有四个答案-99、21、261、1581。你看仅仅是把“加上168”换成“再加上168”差值就从68变成168解的个数也从1个变成4个。这就是为什么读题时一字之差写代码前务必把数学关系确认清楚。以后不管遇到哪个版本用因数分解法都能快速解出还不会漏解。4. Java解法三倒推双循环更通用的视角4.1 思路换个角度枚举暴力法是枚举 x因数分解法是拆因数还有第三种思路直接枚举 m然后用 n² m² 68 去判断。为什么要枚举 m因为 m 是平方根它的取值范围比 x 小得多。根据之前的推导n m 时n² - m² (n - m)(n m)由于 n - m ≥ 1n m ≥ 2m 1所以68 ≥ 2m 1m 最大只能取到 33。也就是说只需要从 0 到 33 枚举 m34次判断就能解决问题。4.2 代码实现与复杂度分析代码长这样public class EnumerateRootSolution { public static void main(String[] args) { int diff 168 - 100; for (int m 0; m 33; m) { long m2 (long) m * m; // 避免 int 乘法溢出 long n2 m2 diff; long n (long) Math.sqrt(n2); if (n * n n2) { long x m2 - 100; System.out.println(m m , n n , x x); } } } }我来解释几个细节(long) m * m这一步很关键。如果 m 是 intm * m 先按 int 计算一旦超过 2^31 - 1 就会溢出结果变成负数。虽然这里 m 最大33不会溢出但培养这种防御习惯很重要尤其是日后处理大数题目。Math.sqrt(n2)的参数是 long会自动转成 double。如果 n2 很大double 精度只有约 15 位十进制有效数字可能出现判断偏差。不过这道题的 n2 最大不超过 33² 68 1157完全在安全范围内。循环上限直接写死成33是因为前面推导已经证明 m ≤ 33。如果你把 diff 换成其他值上限也要重新推导不能照抄。输出结果不变仍然是 x 156。4.3 三种解法对比用表格直观对比一下解法枚举对象循环次数时间复杂度优点缺点暴力枚举x约1170次O(N)思路直接最贴合题目字面需要事先确定范围否则容易瞎猜上界因数分解68的因数不到10次O(√D)数学思路最漂亮不遗漏解需要掌握同奇偶筛选逻辑倒推枚举m34次O(√D)代码短判断逻辑直观需要先推导 m 的上界三种方法各有定位新手先写暴力法理解题意面试时写因数分解法展示思维层次工程上做通用工具时用倒推枚举法最不容易出错。提示如果你要把解法做成一个通用的“平方差等于 D 的整数对查找器”因数分解法是最稳的因为它的循环次数只跟 D 的因数个数有关并且天然不会漏解。5. 实战中的坑与常见问题速查5.1 完全平方数判断的精度问题这是我在实际代码评审里看到最多的问题。很多人写判断正方形是这样写的double sqrt Math.sqrt(num); if (sqrt (int) sqrt) { return true; }这段代码在小整数范围内能用但有两个隐患(int) sqrt是把 double 强转成 int如果 sqrt 非常接近一个整数但比整数小一点点强转会得到比实际整数小1的数导致误判。double 在表达极大整数时精度不足。当 num 超过 2^53 时甚至 num 本身转成 double 就会丢精度。稳妥写法我之前已经给过先算 int sqrt (int) Math.sqrt(num)再判断 sqrt * sqrt num。或者干脆用 BigDecimal 做完全限定判断不过那道题用不上。5.2 整数溢出风险这道题的中间变量虽然不大但稍微改版就可能撞上溢出。比如改成“加上1000000后是平方数加上2000000后也是平方数”m 和 x 都会大不少int 乘法很容易出问题。我的习惯是所有可能先乘后判的中间量都声明成 long。Java 里 long 的范围比 int 大太多在小题目里基本等于“免费保险”。如果真的遇到更大范围那就要考虑用java.math.BigInteger了不过那是另一个场景的事。5.3 负数范围与零的处理很多初学者忽略 x 可以是负数。这道题里 x -168 就是一个边界值因为 x 168 0 0²但 x 100 -68不是平方数。把所有边界情况都考虑一遍才算完整解题。还有 m、n 取负数的问题。m -16 时m² 同样是256不影响 x。所以因数分解法里我默认 m、n 取非负整数最终 x 的结果不变。如果你想跟面试官讨论这个点可以主动提一句因为平方的符号不影响结果所以非负解已经覆盖所有情况。5.4 面试里怎么答才算加分这道题在很多面试里不是笔试题而是口述题。面试官可能一边喝茶一边问你这个数是多少我建议的回答节奏是先说出数学关系设 x 100 m²x 168 n²。然后相减得到 n² - m² 68。接着因式分解68 2 × 34所以 n - m 2n m 34。解出 n 18m 16x 156。最后验证156 100 256156 168 324。整个过程大概一分钟不用写一行代码。如果你一上来就说“我循环跑一下”面试官心里的评分至少降一档。这道题考察的核心不是你会不会用 Java而是你有没有把问题数学化的意识。6. 个人经验与扩展建议这道题我几乎每年都会用不同的语言重写一遍每次都会有新的感受。最早我写 Python 版本的时候用的就是暴力循环上界拍脑袋写了十万结果跑完还怀疑是不是漏了解。后来做了数学推导才发现上界一千都不到。那种“豁然开朗”的感觉让我养成了一个习惯拿到算法题先别碰键盘用纸笔把约束条件理清楚尤其是变量之间的数量关系。如果你打算把这类题整理成一套通用工具可以沿这个方向扩展输入一个差值 D 和基准偏移量 offset输出所有满足 (x offset) 与 (x offset D) 均为完全平方数的整数 x。核心思路就是因数分解 同奇偶筛选。我之前写过一个这样的方法核心代码只有十几行却能处理一整个系列的“平方差”题目效果很香。另外我想把这道题再往深处挖一点当你把 D 固定后x 的解其实很有限因为 n - m ≥ 1 决定了 m 是有限集。遇到这类“两条件都是平方数”的问题都可以先转换成平方差再用因数分解收束范围。这个方法不局限于 JavaC、Python、JavaScript 都适用。最后再分享一个小经验写完代码后不要只看输出结果就收工。手动把等式代回去验证一遍是成本最低的防错手段。我见过有同学因为 m、n 的符号问题答案输出了一堆重复项就是因为缺了最后的数学验证。这道题里的 156 虽然简单但验证步骤传递的习惯在以后处理更复杂的数学编程题时价值会成倍放大。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
