268. 丢失的数字

;(function () {
  /**
   * 268. 丢失的数字
   * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
   *
   * 输入：nums = [3,0,1]
   * 输出：2
   * 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
   *
   * 输入：nums = [0,1]
   * 输出：2
   * 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
   *
   * 输入：nums = [9,6,4,2,3,5,7,0,1]
   * 输出：8
   * 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
   *
   * 输入：nums = [0]
   * 输出：1
   * 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
   *
   */

  function missingNumber(nums: number[]): number {
    // 方法一：
    // let len = nums.length;
    // nums.sort((a, b) => a - b)
    // for(let i = 0; i < len; i++) {
    //     if (i !== nums[i]) {
    //         return i
    //     }
    // }
    // return len

    // 方法二： ------ 比方法一更耗时 ----------
    // let len = nums.length;
    // for (let i = 0; i < len; i++) {
    //     if (!nums.includes(i)) {
    //         return i
    //     }
    // }
    // return len

    // 方法三；哈希
    // const set = new Set();
    // const len = nums.length;
    // for(let i = 0; i < len; i++) {
    //     set.add(nums[i])
    // }
    // for(let j = 0; j <= len; j++) {
    //     if (!set.has(j)) {
    //         return j
    //         break;
    //     }
    // }
    // return -1

    // 方法四：位运算

    // 方法五；数学（高斯求和）
    const n: number = nums.length
    const total: number = Math.floor((n * (n + 1)) / 2)
    let addSum: number = 0
    for (let i = 0; i < n; i++) {
      addSum += nums[i]
    }
    return total - addSum
  }

  let nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
  console.log(missingNumber(nums))
})()