题目
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
注意:本题相对书上原题稍作改动
示例 1:
输入:[3,0,1] 输出:2
示例 2:
输入:[9,6,4,2,3,5,7,0,1] 输出:8
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/missing-number-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解思路
可以知道数组应该是从0到n 一共n+1个数 那么就可以知道这些数的总和为
(
n
∗
(
n
+
1
)
)
2
\frac{(n*(n+1))}{2}
2(n∗(n+1)) 那么把已知的数的总和算出来,被上面的总和减去,就得到缺省的数字是多少。
代码
class Solution {
public:
int missingNumber(vector
int num = (nums.size()*(nums.size()+1))/2;
int sum = 0;
for(int i=0;i { sum+=nums[i]; } return num -sum; } }; 相关链接
发表评论