LeetCode 442：找到数组中的重复项

文章来自我的公众号，欢迎关注: LeetCode 442：找到数组中的重复项

问题：

给定一个整数由组成的数组，其中 1 ≤ a[i] ≤ n (n 是数组长度)，数组中有些元素会出现两次，而有些只出些一次。

找到这个数组中出现过两次的元素。

示例：

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

输出:
[2,3]

解析：

一个简单的解题思路是，将数组元素放在频率字典中(map)，最后取出字典中频率大于1的元素即可。

TypeScript 代码：

function findDuplicates(nums: number[]): number[] {
    return nums.filter(function (this: Set<number>, v: number) {
        if (this.has(v)) {
            return true;
        }
        this.add(v);
    }, new Set());
}

这里我们使用了 Set ：凡是之前加过的元素都是重复的。

另外一个解答思路就比较讨巧了。

考虑到数组元素满足条件 1 ≤ a[i] ≤ n，那么 a[a[i]-1] 一定也是数组中的元素，因为 a[i]-1 下是数组所有下标的集合。

试想一下，如果我们在遍历过程中将 a[i]-1 对应的元素取反，后续遍历中如果存在 a[j] 等于 a[i]，那么 a[j]-1 对应的元素一定是负数，此时 a[j] 就是那个出现了2次的元素。需要注意的是，遍历过程中后面的元素可能在之前被取反过，所以在应用 a[i]-1 时，要用 a[i] 的绝对值，即 Math.abs(a[i])-1。

以数组 [2,1,1] 做推导示例：

当遍历到最后一个元素 1 时，发现之前有元素将 0 (即 1-1 ) 这个位置的元素变为负数了，所以 1 是重复的元素。

TypeScript 代码如下：

function findDuplicates(nums: number[]): number[] {
    return nums.reduce((p, v, i, a) => {
        // 当前元素的绝对值，防止之前被取反过
        const val = Math.abs(v);
        // 需要被取反的元素
        const target = val - 1;

        // 如果该元素已经被取反过，说明 val 是重复的元素，加入到返回值中
        // 否则进行取反操作
        a[target] < 0 ? p.push(val) : (a[target] = -a[target]);
        return p;
    }, [] as number[]);
}

上面两段代码中分别用到了 Array 对象的 filter 和 reduce 方法，在解决实际问题时，它们相当有用。

- END -