LeetCode - Missing Number

LeetCode 的 Missing Number 題目如下:

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?


簡單的說該方法會被帶入一個陣列,裡面的元素為 0 到 n 不重複的數值,需找到並回傳該陣列缺少的數值。像是如果帶入的陣列是 [0, 1, 3],該陣列跳過了 2,所以回傳值會是 2。


因為長度為 n 的陣列如果沒有跳號,裡面的元素應該是 0, …, n,且缺少的數值只有一個。所以我們可以把帶入的陣列跟本來預期的值相減後加總,然後用陣列的長度與之相減。

1
2
3
4
5
6
7
8
9
public class Solution {
public int MissingNumber(int[] nums) {
var sum = 0;
var length = nums.Length;
for (var i = 0; i < length; i++)
sum += nums[i] - i;
return length - sum;
}
}