# use space - hashset
    #   - time: O(n)
    #   - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = set()
        for num in nums:
            s.add(num)

        for v in range(0, len(nums) + 1):
            if v not in s:
                return v

    # XOR（异或）
    #  3 ^ 3 -> 0（相同元素会被抵消掉）
    #  3 ^ 0 -> 3（和0 XOR 会得到其本身）
    #  3 ^ 2 ^ 1 = 3 ^ 1 ^ 2（顺序不影响）
    # - time: O(n)
    # - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = len(nums)
        for i in range(len(nums)):
            res = res ^ nums[i] ^ i
        return res
      
    # math - sum
    #  比如 n = 3, [0,1,2,3] 的和 减去 目标数组的和（比如 [1,2,3] 或者 [0,1,2]），就可以得到缺失的元素
    # - time: O(n)
    # - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(len(nums)):
            res = res + i - nums[i]
        return res + len(nums)
      
     # Negative Marking - 解法太复杂了，就简单的办法 
    # - time: O(n)
    # - space: O(1)，把 input array 用作 memory space
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        n = len(nums)
        # Init memorised flags to be positive, i.e., we use positive to memorised a corresponding val existing
        for idx in range(n):
            if nums[idx] == 0:
                # Use u + 1 to replace 0, because
                #   1. 0 cannot record being positive or negative
                #   2. set it to be n + 1 doesn't affect the final result
                nums[idx] = n + 1

        # Memorise flags for each val
        for i in range(n):
            val = abs(nums[i])
            if val != n + 1:  # If the val is n + 1, we don't need to care
                idx = val - 1
                nums[idx] = -nums[idx]

        # Check whether a specified val exists or not by checking its corresponding memorised flag
        for idx in range(n):
            if nums[idx] > 0:
                val = idx + 1
                return val
        return 0  # If [1, n] all exist, meaning 0 doesn't exist