Дан массив целых чисел nums, содержащий n целых чисел в диапазоне [0,n] включительно. Необходимо найти число из диапазона, которого не хватает в этом массиве.
В массиве nums гарантированно отсутствует только одно число, остальные встречаются ровно один раз.
Пример 1:
Ввод: nums = [3,1,5,0,2] Вывод: 4 Объяснение: в массиве есть все числа от 0 до 5, кроме 4.
Пример 2:
Ввод: nums = [1,2] Вывод: 0
Ограничения:
len(nums) >= 10 <= nums[i] <= len(nums)public class Solution
{
public static int MissingNumber(List<int> nums)
{
int n = nums.Count;
int overallSum = n * (n + 1) / 2; // сумма чисел от 0 до n
int actualSum = 0;
foreach (int num in nums)
{
actualSum += num;
}
return overallSum - actualSum;
}
}#include <vector>
using namespace std;
int missingNumber(const vector<int>& nums) {
int n = nums.size();
int overallSum = n * (n + 1) / 2; // сумма чисел от 0 до n
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
return overallSum - actualSum;
}package main
func missingNumber(nums []int) int {
n := len(nums)
overallSum := n * (n + 1) / 2 // сумма чисел от 0 до n
actualSum := 0
for _, num := range nums {
actualSum += num
}
return overallSum - actualSum
}import java.util.List;
public class Solution {
public int missingNumber(List<Integer> nums) {
int n = nums.size();
int overallSum = n * (n + 1) / 2; // сумма чисел от 0 до n
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
return overallSum - actualSum;
}
}from typing import *
def missing_number(nums: List[int]) -> int:
n: int = len(nums)
overall_sum = n * (n + 1) // 2 # сумма чисел от 0 до n
return overall_sum - sum(nums)export function missingNumber(nums) {
const n = nums.length;
const overallSum = (n * (n + 1)) / 2; // сумма чисел от 0 до n
return overallSum - nums.reduce((a, b) => a + b, 0);
}Оценка сложности
O(n), где n - длина массива numsO(1)