方法一：如何用“和 + 平方和”在 O(N)/O(1) 内求出缺失的两个数？请给出推导与求解步骤。

Method 1: How do you use 'sum + sum of squares' to find the two missing numbers in O(N) time and O(1) space? Provide derivation and steps.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms

标签: sum, sum of squares, quadratic

参考答案摘要

答案 设缺失的两个数为 a、b。令 S = 1..N 的总和，Q = 1..N 的平方和；遍历 nums 得到 s = nums 的和，q = nums 的平方和。 则有：a + b = (S - s) = A；a^2 + b^2 = (Q - q) = B。 又因为 (a + b)^2 = a^2 + b^2 + 2ab，所以 ab = (A^2 - B) / 2。 于是 a、b 是方程 x^2...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。