你的位置:首页 > Java教程

[Java教程][LeetCode] Missing Number (A New Questions Added Today)


Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

 

     这道题的话其实为了简单一点是需要用到一些数学知识的。我们已知的是这里面只有一个missing的数。

     如果给你一个连续的整数列,计算总的sum的公式=[总个数*(总个数+1)]/2。

     那么简化一点,先计算出应该有的sum然后减去现在的sum,得到的差就应该是那个我们miss的数了。

     注意一点,我们的数列是从0开始,但是计算本应的sum的时候依然应该是[nums.length*(nums.length+1)]/2来计算,因为我们要加上一位作为被miss的数的位置。所以结果就是总个数还是nums.length不变。

     代码如下。~

public class Solution {  public int missingNumber(int[] nums) {    int sum=0;    for(int i=0;i<nums.length;i++){      sum=sum+nums[i];    }    return (nums.length*(nums.length+1))/2-sum;      }}