题目描述
给定一个包含从 1 到 n 的整数的数组 nums，其中 n 是数组的长度。数组中的元素都不相同，但是缺失了一个数字，导致数组和为 n*(n+1)/2 减去的某个数字。找出这个缺失的数字。
示例
示例 1
输入: nums = [3,0,1]
输出: 2
示例 2
输入: nums = [0,1,3]
输出: 2
示例 3
输入: nums = [9,6,4,2,3,5,7,0,1]
输出: 8
题解
这个问题可以通过数学公式来解决。根据等差数列求和公式，我们知道从 1 到 n 的整数和为 n*(n+1)/2。因此，我们可以通过计算数组中所有数字的和，然后从总和 n*(n+1)/2 中减去这个值来找到缺失的数字。
- 计算总和：计算数组 nums 中所有数字的和。
- 计算缺失的数字：使用公式 n*(n+1)/2 - sum 来计算缺失的数字，其中 n 是数组的长度，sum 是数组中数字的和。
- 返回结果：返回计算出的缺失数字。
代码实现
int missingNumber(vector<int>& nums) {int n = nums.size();int totalSum = n * (n + 1) / 2;int arraySum = 0;for (int num : nums) {arraySum += num;}return totalSum - arraySum;
}
复杂度分析
● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组来计算和。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到缺失的数字，且不需要额外的存储空间。