Leetcode topic [array] -268- missing numbers

Force link ：https://leetcode-cn.com/probl...
Their thinking ：

1. It's still the old way , Look at the questions , Look for clues , The first question is to include [0,n] Array of numbers for , find [0,n] There are no numbers in the array . So if [0,n] All the numbers in are in , It must be shaped like [0,1,2,3,4...,n-1,n] Such adjacent increasing numbers
2. Looking for a regular ： In such numbers , First sort them , After sorting, the subscript and number are equal , So first you can traverse the array , If you traverse to a subscript , The number is not equal to it , Then the number does not exist

func missingNumber(nums []int) int {
    for i, v := range nums {
        if i != v {
            return i
        }
    }
    return len(nums)
}

3. The above ideas can be further extended , Use hash table for optimization , First, take the numbers in each array as numbers KEY,TRUE by value marked , Then carry out a from 0~ Traversal of upper bound ,m[i] by false This number is missing

func missingNumber(nums []int) int {
    numToBool := make(map[int]bool, len(nums))
    for i := 0; i < len(nums); i++ {
        numToBool[nums[i]] = true
    }
    for i := 0; ; i++ {
        if !numToBool[i] {
            return i
        }
    }
    return len(nums)
}

4. The most ingenious solution , It's mathematics ！ Since childhood, we have known Gauss, the little prince of Mathematics , From 0~n The formula for the sum of integers ：sum = n * (n + 1) / 2; So from 0 To n The number of , What is missing is the sum of the number you should have minus the array ：

func missingNumber(nums []int) int {
    n := len(nums)
    total := n * (n + 1) / 2
    sum := 0
    for i := 0; i < n; i++ {
        sum += nums[i]
    }
    return total - sum
}