2021.10.02 - 108.丢失的数字

• 1. 题目
• 2. 思路
• • (1) 数学法
  • (2) 数学法优化
  • (3) 位运算
• 3. 代码

• 根据题目条件，缺失的数字必然等于0_{n之和减去nums[0]}nums[n-1]之和。

• 与(1)的思想基本相同，可以在遍历时加减同时进行，避免溢出。

• 与(2)的思想基本相同，将加减运算替换为异或运算即可。

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int sum = (1 + len) * len / 2;
        for (int i = 0; i < len; i++) {
            sum -= nums[i];
        }
        return sum;
    }
}

class Solution1 {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += (i + 1 - nums[i]);
        }
        return res;
    }
}

class Solution2 {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= ((i + 1) ^ nums[i]);
        }
        return res;
    }
}