前言說明
算法學(xué)習(xí)，日常刷題記錄。
題目連接
題目內(nèi)容
給定一個數(shù)組，包含從1到N所有的整數(shù)，但其中缺了兩個數(shù)字。你能在O(N)時間內(nèi)只用O(1)的空間找到它們嗎？
以任意順序返回這兩個數(shù)字均可。
示例1:
輸入: [1]
輸出: [2,3]
示例2:
輸入: [2,3]
輸出: [1,4]
提示:
nums.length <= 30000
分析過程
思路：使用總和累減法，用總和累減法可以找出缺失的一個數(shù)字，而這里缺失的是兩個數(shù)字，那么先用總和累減法找出缺失的兩個數(shù)字的總和，總和除以2，確定切分的位置，切分為兩部分后，兩部分各缺失一個數(shù)字，第一部分再用總和累減法找出缺失的那個數(shù)字，再用原來缺失的兩個數(shù)字的總和減去找到的這個缺失的數(shù)字得到另一個缺失的數(shù)字，即可找到缺失的兩個數(shù)字。
第一步
計算整數(shù)范圍的長度size，因為是缺失兩個數(shù)字，所以整數(shù)范圍的長度是數(shù)組長度加2。
計算從1到N的總和sum，總和 = (首項 + 末項) * 數(shù)量 / 2。
第二步
遍歷數(shù)組，使用總和累減法，即用1到N的總和sum逐個減去數(shù)組的元素，最后得到缺失的兩個數(shù)字的總和，這時sum變成缺失的兩個數(shù)字的總和。
第三步
把缺失的兩個數(shù)字的總和sum除以2等于mid，因為題目說包含從1到N所有的整數(shù)，所以數(shù)字不重復(fù)，缺失的兩個數(shù)字一定是一個小于等于mid，另一個大于mid。
為何一個是小于等于mid？因為java中除以2，如果結(jié)果是小數(shù)，那么會去掉小數(shù)點后的位向下轉(zhuǎn)轉(zhuǎn)換。例如：缺失的兩個數(shù)字是7和8，那么sum=15，15/2=7，這里就出現(xiàn)小于等于mid，而且從這里也可以看出，mid一定落在1到N的整數(shù)之間，因為1到N是連續(xù)的整數(shù)。
所以，數(shù)組被mid切分為了兩部分，兩部分各分布一個缺失的數(shù)字。
第四步
計算第一部分的總和sum1，即從1到mid的總和，總和 = (首項 + 末項) * 數(shù)量 / 2，這里的首項就是1，末項也是1，數(shù)量就是mid，即sum1 = (1 + mid) * mid / 2。
第五步
計算第一部分在數(shù)組中的總和sumOfLessMid，通過遍歷數(shù)組，累加得到，遍歷時小于等于mid的數(shù)字才是符合條件進行累加的，遍歷數(shù)組結(jié)束后，sumOfLessMid就是第一部分在數(shù)組中的總和。
第六步
定義第一部分中缺失的數(shù)字為one，定義第二部分中缺失的數(shù)字為two。
第一部分中缺失的數(shù)字 = 第一部分的總和 - 第一部分在數(shù)組中的總和，即one = sum1 - sumOfLessMid。
第一部分中缺失的數(shù)字計算出來后，那么用前面缺失的兩個數(shù)字的總和sum減去第一部分中缺失的數(shù)字one，就算出了第二部分中缺失的數(shù)字two。
第二部分中缺失的數(shù)字 = 缺失的兩個數(shù)字的總和 - 第一部分中缺失的數(shù)字，即two = sum - one。
最后返回兩個缺失的數(shù)字one和two組成的數(shù)組。
解答代碼
class Solution {
public int[] missingTwo(int[] nums) {
// 思路：總和累減法，用總和累減法可以找出缺失的一個數(shù)字，而這里缺失的是兩個數(shù)字，那么先用總和累減法找出缺失的兩個數(shù)字的總和，總和除以2，確定切分的位置，切分為兩部分后，兩部分各缺失一個數(shù)字，第一部分再用總和累減法找出缺失的那個數(shù)字，再用原來缺失的兩個數(shù)字的總和減去找到的這個缺失的數(shù)字得到另一個缺失的數(shù)字，即可找到缺失的兩個數(shù)字，不過這種方法先要保證不能總和不能溢出
// 定義整數(shù)長度，因為缺失兩個數(shù)字，所以整數(shù)范圍是數(shù)組長度加2
int size = nums.length + 2;
// 計算從1到n的總和，總和=(首項+末項)*數(shù)量/2
int sum = (1 + size) * size / 2;
// 遍歷數(shù)組，總和累減數(shù)組的整數(shù)，最后得到缺失的兩個數(shù)字的總和
for (int num : nums) {
sum -= num;
}
// 這時sum變成缺失的兩個數(shù)字的總和
// 缺失的兩個數(shù)字的總和除以2，因為數(shù)字不重復(fù)，所以缺失的兩個數(shù)字一個小于等于mid，另一個大于mid
int mid = sum / 2;
// 數(shù)組被切分為了兩部分，兩部分各分布一個缺失的數(shù)字
// 計算第一部分的總和，即從1到mid的總和，總和=(首項+末項)*數(shù)量/2
int sum1 = (1 + mid) * mid / 2;
// 定義第一部分在數(shù)組中的總和
int sumOfLessMid = 0;
// 遍歷數(shù)組，累加得到第一部分在數(shù)組中的總和
for (int num : nums) {
if (num <= mid) {
// 小于等于mid的數(shù)字是符合條件的
sumOfLessMid += num;
}
}
// 第一部分中缺失的數(shù)字=第一部分的總和-第一部分在數(shù)組中的總和
int one = sum1 - sumOfLessMid;
// 第二部分中缺失的數(shù)字=缺失的兩個數(shù)字的總和-第一部分中缺失的數(shù)字
int two = sum - one;
// 返回兩個缺失的數(shù)字組成的數(shù)組
return new int[]{one,two};
}
}
提交結(jié)果
執(zhí)行用時1ms，時間擊敗100.00%的用戶，內(nèi)存消耗39.9MB，空間擊敗61.54%的用戶。
原文鏈接
原文鏈接：消失的兩個數(shù)字
