LeetCode题练习与总结：丢失的数字--268
一、题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 10^40 <= nums[i] <= nnums中的所有数字都 独一无二
二、解题思路
- 首先，我们可以利用等差数列求和公式计算 [0, n] 范围内所有数的和，其中 n 是数组
nums的长度。 - 然后，我们遍历数组
nums，将每个元素从等差数列的和减去，剩下的数就是缺失的数字。
三、具体代码
class Solution {public int missingNumber(int[] nums) {// 计算等差数列的和，即[0, n]的和int n = nums.length;int total = (0 + n) * (n + 1) / 2;// 遍历数组，减去每个元素for (int num : nums) {total -= num;}// 剩下的数就是缺失的数字return total;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
计算等差数列的和：这一步是一个常数时间的操作，因为它只涉及几个基本的算术运算（加法、乘法和除法），与输入数组
nums的大小无关。因此，这一步的时间复杂度是 O(1)。 -
遍历数组
nums：这一步涉及一个循环，该循环会遍历数组中的每个元素一次。如果数组的大小是 n，那么循环将执行 n 次。因此，这一步的时间复杂度是 O(n)。
综合上述两步，算法的总时间复杂度是 O(n)，因为 O(1) + O(n) = O(n)。
2. 空间复杂度
-
变量
n和total：这两个变量都是基本数据类型（整型），它们占用的空间不随输入数组nums的大小而变化。因此，它们的空间复杂度是 O(1)。 -
输入数组
nums：虽然这个数组本身在算法中是输入，但是空间复杂度分析通常只考虑算法额外使用的空间。因此，输入数组的空间不计入算法的空间复杂度。
综上所述，算法的总空间复杂度是 O(1)，因为它只使用了固定数量的额外空间。
五、总结知识点
-
类定义 (
class Solution): 这是Java中的类定义语法，表明我们定义了一个名为Solution的类。 -
方法定义 (
public int missingNumber(int[] nums)): 这是Java中定义方法的语法，表明我们定义了一个名为missingNumber的公共方法，它接受一个整数数组nums作为参数，并返回一个整数。 -
数组长度获取 (
int n = nums.length): 这是获取数组长度的方法，length是数组的一个属性，它返回数组的元素数量。 -
算术运算 (
int total = (0 + n) * (n + 1) / 2): 这里使用了加法、乘法和除法来计算等差数列的和，遵循算术运算的优先级规则。 -
循环遍历 (
for (int num : nums)): 这是一个增强型for循环，用于遍历数组nums中的每个元素，每次循环将数组中的一个元素赋值给变量num。 -
赋值运算 (
total -= num): 这是赋值运算符的用法，它等同于total = total - num，用于从total中减去当前遍历到的数组元素。 -
返回语句 (
return total;): 这是Java中返回方法结果的语法，表示将total的值作为方法的返回值。 -
整型数据类型 (
int): 在这个方法中，所有的变量都是int类型，这是Java中用于表示整数的原始数据类型。 -
逻辑顺序 (
//注释): 代码中使用了注释来解释代码的逻辑，虽然注释不是Java语言的一部分，但它们对于代码的可读性和维护性是非常重要的。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。