（美团）巧用数组下标，轻轻松松找出所有元素

大家好，我是吴师兄。

今天分享的算法题和 数组 这个数据结构有关，如果你不了解数组的特点，你百分百无法想到它的解法。

题目描述

给定一个整数数组 a，其中 1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在 O(n) 时间复杂度内解决这个问题吗？

示例：

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

输出:
[2,3]

来源：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array

题目解析

输入数组包含值为 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
}