题目描述

题目描述

image.png
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题？

思路

等差数列求和，和数组的差就是缺少的那个数

  1. public int missingNumber(int[] nums) {
  2.     // 等差数列求和公式
  3.     int sum = (nums.length + 1) * nums.length / 2;
  4.     for (int num : nums) {
  5.         sum = sum - num;
  6.     }
  7.     return sum;
  8. }

可以采用异或运算

  1. public int missingNumber(int[] nums) {
  2.     int rs = 0;
  3.     for (int i = 0; i < nums.length; i++) {
  4.         rs = rs ^ i;
  5.         rs = rs ^ nums[i];
  6.     }
  7.     rs = rs ^ nums.length;
  8.     return rs;
  9. }