首页leetcode 268

leetcode 268

时间: 2025-03-29 20:16:23 浏览: 32

### LeetCode Problem 268 Missing Number LeetCode 的第 268 题名为 **Missing Number**，其题目描述如下：给定一个包含 `[0, n]` 中 `n` 个数的数组 `nums`，找出其中缺失的那个数字。 #### 示例 ```plaintext 输入: nums = [3,0,1] 输出: 2 解释: 数组中缺少数字 2。 ``` 此问题可以通过多种方法解决，以下是两种常见的解决方案：一种基于求和公式的方法以及另一种利用位运算的技术。 --- #### 方法一：数学公式法通过计算完整的序列总和减去实际存在的元素之和来找到缺失的数字。对于长度为 `n` 的数组，理想情况下应有 `(n * (n + 1)) / 2` 的总和[^6]。实现代码如下所示： ```python class Solution: def missingNumber(self, nums): expected_sum = len(nums) * (len(nums) + 1) // 2 actual_sum = sum(nums) return expected_sum - actual_sum ``` 这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)[^7]。 --- #### 方法二：位运算法可以使用异或操作符 (`XOR`) 来解决问题。由于 XOR 运算具有交换律和结合律，并且任何数与其本身做 XOR 结果都为零，因此我们可以将索引与数值配对并执行 XOR 操作以得到最终结果[^8]。具体实现如下： ```python class Solution: def missingNumber(self, nums): xor = 0 i = 0 for i in range(len(nums)): xor ^= i ^ nums[i] return xor ^ i + 1 ``` 该方法同样具备时间复杂度 O(n) 和空间复杂度 O(1) 的特性[^9]。 --- #### 总结上述两种方式均能有效处理这个问题，选择哪种取决于个人偏好或者特定场景下的需求。如果更关注可读性和简洁性，可能倾向于采用数学公式的方案；而当希望减少溢出风险时，则可以选择位运算的方式。 ---

阅读全文