>[success] # 數組中重復的數據 * 題目描述 給你一個長度為 n 的整數數組 nums ，其中 nums 的所有整數都在范圍 [1, n] 內，且每個整數出現 一次 或 兩次 。請你找出所有出現 兩次 的整數，并以數組形式返回。 * 要求 你必須設計并實現一個時間復雜度為 O(n) 且僅使用常量額外空間的算法解決此問題。 來源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/find-all-duplicates-in-an-array >[danger] ##### 第一次解題思路 第一次解題時候想到使用`Map` 結構來進行計算保存出現的次數，雖然解題出來了但是不滿足題中要求的空間復雜度`O(1)` ,看了一些大佬使用先排序然后相同數字相同取出的辦法排序的時間復雜度是 `O(N?log(N))`不符合題目的時間復雜度`(N)` * 第一次 js 解題代碼 ~~~ /** * @param {number[]} nums * @return {number[]} */ var findDuplicates = function(nums) { const countMap = {} return nums.reduce((acc,cur)=>{ if(!countMap[cur]) countMap[cur] = 0 ++countMap[cur] // 出現兩次 if(countMap[cur]===2){ acc.push(cur) } return acc },[]) }; ~~~ >[info] ## 題解 在空間想符合`O(1)` 那需要`原地去修改數組`，題目中說數組中的數字不會大于數組的長度，因此數組中`每項減一`都會在當前數組中找到`對應項`  如果將遍歷對`應項映射腳標`所`對應的值取反`做標記,當如果再有同樣`應項映射腳標`所`對應的值`為負數時候說明已經在當前數組找過一次因此可以斷定為重復值 * 前半程映射  * 后半程映射  >[danger] ##### js 解題 ~~~ var findDuplicates = function (nums) { return nums.reduce((acc, cur, index, arr) => { // 獲取下角標，因為下角標被變成負數因此需要做絕對值 const key = Math.abs(cur) arr[key - 1] *= -1 // 判讀大于等于0說明出現第二次 從負數變為整數 if (arr[key - 1] >= 0) { acc.push(key) } return acc }, []) } ~~~ >[danger] ##### java ~~~ java import java.util.List; import java.util.ArrayList; public class Solution { public List<Integer> findDuplicates(int[] nums){ List<Integer> res = new ArrayList<>(); for(int i=0;i< nums.length;i++){ // 下角標key int key = Math.abs(nums[i]); // 對應值映射的下角標存儲的值變為負數 nums[key-1]*=-1; if(nums[key-1]>=0){ res.add(key); } } return res; } } ~~~ >[info] ## 題解二 整體思路和`題解一思想是一樣`的只要`通過某種形式將反復出現值進行操作`，和`單次操作`的值進行`對比`取出`雙次操作`的值即可 將`對應值`所映射的`腳標值`這次從取反變成`加當前數組長度`,如果出現兩次那么就會`加兩次當前數組長度值`，那么出現`兩次值所映射對應值`一定會`大于當前長度的兩倍` 剩下問題就是之前只是單純的取反，因此獲取值的時候`index`只需要獲取`絕對值`即可找到對應映射值，現在思路就是需要利用`取余進行`,即**index=(當前值-1)%長度** **注**: (值)取余(取余值) 值 < 取余值 取余結果為**值** 舉個例子 **6 % 7 = 6**   >[danger] ##### js 解法 ~~~ // /** // * @param {number[]} nums // * @return {number[]} // */ var findDuplicates = function (nums) { // 將映射值都進行加當前數組長度 const {length} = nums for(let num of nums){ // 取余獲取映射index const index = (num-1) % length nums[index] +=length } // 找到所有大于等于 2*length return nums.reduce((acc,cur,index)=>{ if(cur>length*2) acc.push(index+1) return acc },[]) } ~~~ >[danger] ##### java ~~~ import java.util.List; import java.util.ArrayList; public class Solution { public List<Integer> findDuplicates(int[] nums){ List<Integer> res = new ArrayList<>(); int len = nums.length; // 將數組進行累加當前長度 for(int i=0;i<len;i++){ // 利用取余獲取實際index int idx = (nums[i]-1) % len; nums[idx] +=len; } for(int i=0;i<len;i++){ // 出現兩次會累加兩次當前長度因此會大于2n if(nums[i]>2*len) res.add(i+1); } return res; } } ~~~ >[success] # 總結 為了滿足題中說的空間復雜度達到**常量**級別，因此需要以自身為容器進行，數組在使用上也是和**Map** 一樣是**key value**的結構，因此其實可以將數組抽化為一個映射容器作為計算 類似其他的解題方法，像題中指定了 n 的范圍 `1 <= n <= 10^5` 也可將每個數加10^5,遇到大于10^5 值在減掉和第一種思路一樣只是使用了極限值