LeetCode-268-丟失的數字

丟失的數字

題目描述：給定一個包含 [0, n] 中 n 個數的陣列 nums ，找出 [0, n] 這個範圍內沒有出現在陣列中的那個數。

進階：

• 你能否實現線性時間複雜度、僅使用額外常數空間的演算法解決此問題?

示例說明請見LeetCode官網。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/missing-number/
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。

解法一：陣列遍歷

首先，獲取數字的長度為n，根據根據公式n*(n+1)/2得到從0到n的數字相加之和為sum，由於nums陣列中只缺少一個數，所以遍歷陣列，將sum減去陣列中所有的元素，然後剩下的數字就是要返回的數。

public class LeetCode_268 {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n * (n + 1) / 2;
        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println(missingNumber(nums));
    }
}

【每日寄語】 最清晰的腳印，總是印在最泥濘的路上。