題目：
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?

翻譯：
給定一個數組，包含n個不同的數，從0, 1, 2, …, n里面取出，找到那個缺失的數。
提示:你的程序應該運行在一個線性的時間復雜度上。你可以實現它僅僅使用常量的額外空間復雜度嗎？

分析：
按照題意，數組只缺失了一個數，來構成數列0, 1, 2, …, n，由于數組可能是亂序的，如果按照傳統方法遍歷，將需要先做排序（增加時間復雜度），或者使用額外空間來記錄（增加空間復雜度）。
由于只缺少了一個數，我們可以把未缺失的原數列的和計算出來，與數組的和對比，差值即缺失的數。

代碼：

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

總結

以上是生活随笔為你收集整理的Leet Code OJ 268. Missing Number [Difficulty: Medium]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。