題目描述

給定一個整數數組 a，其中 1 ≤ a[i] ≤ n （n為數組長度）, 其中有些元素出現兩次而其他元素出現一次。

找到所有出現兩次的元素。

你可以不用到任何額外空間并在 O(n) 時間復雜度內解決這個問題嗎？

示例：

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[2,3]

題目解析

輸入數組包含值為 1 ～ n（n 是數組的長度）的元素。這里面有的元素出現了兩次，有的元素出現了一次，找出那些出現兩次的元素。最后，題目還加了實現上的限制條件，那就是不能使用額外的空間，而且時間必須在 O(n) 內。

首先還是考慮常規的解法，也就是沒有時空上面的限制條件的話，你會如何來解題？

如果沒有空間上面的限制，那么我們完全可以使用哈希表來進行操作，也就是先用哈希表統計每個元素出現的個數，然后遍歷一遍哈希表找出那些出現兩次的元素即可，這么下來時間上也是滿足條件的，但就是用到了額外的空間。

還有一種思路是排序，排序后，相同的元素會緊挨在一起。在遍歷一遍數組，根據元素的相鄰元素來找出那些出現兩次的元素。這么下來雖說沒有用到額外的空間，但是因為有排序，時間并不在 O(n) 內。

上面的那兩種思路都是常規的思路，一般有一點編程經驗的人都能想得到。

那要如何做才能既滿足空間又滿足時間呢？

因為題目給的信息并不復雜，就是一個整形數組，那么我們就要借助整形數組本身來解題。

數組本身其實就兩個信息，一個是下標，另一個是元素的值。那么我們就需要構建下標和元素的值的聯系。

你可能會說，下標和元素的關系不是很直白嗎？我們通過下標可以直接找到元素，下標就是元素的索引。對，沒錯，但是不知道你有沒有發現數組里的元素的值的范圍是在 [0, n] 之間的。

這也就為反向從元素值本身出發定位到下標提供了可能，如果有兩個元素都定位到了同一個下標，那說明什么？

說明了這個元素出現過兩次，我們就需要記錄下來。

剩下的問題就是，“如何記錄次數呢？”。

因為數組里的元素要么出現了一次，要么出現了兩次，其實不用記錄完整的次數。每當遍歷到一個元素，我們只需要標記一下這個元素對應的下標出現過即可，那么下一次另外一個元素定位到同樣的下標就可以確定之前有遍歷到相同的元素。

那怎么標記才不會使元素失去其原本的意義呢？答案是直接取反。

參考代碼

func findDuplicates(nums []int) []int {
    if len(nums) == 0 {
        return []int{}
    }

    results := []int{}

    for i := 0; i < len(nums); i++ {
        // 獲得元素 “匹配” 的下標
        // 因為有可能被取反過，所以這里取個絕對值
        index := abs(nums[i]) - 1

        // 當元素對應的下標的元素被取反
        // 說明該元素之前出現過，需要記錄
        if nums[index] < 0 {
            results = append(results, index + 1)
        }

        // 標記，取反
        nums[index] = -nums[index]
    }

    return results;
}

func abs(a int) int {
    if a < 0 {
        return -a
    }

    return a
}