在 JavaScript 数组中查找第一个重复项

在这篇博文中，我们将探讨一个软件工程师在面试中可能会遇到的问题的解决方案背后的思考过程：如何在数组（整数、字符串或其他类型）中找到第一个重复元素。

虽然这个问题可能比你在面试中直接遇到的问题要简单一些，但我们用来解决这个问题的核心概念（以及提出这个问题的过程）将适用于以后更复杂的问题。

准备好了吗？出发！

首先，让我们明确一下我们设想的提示是什么：

给定一个包含整数、字符串或混合数据类型的数组，找出数组中第一个重复元素，使得该元素第二次出现的索引最小。如果存在多个重复元素，则返回第二次出现的索引小于其他元素第二次出现的索引的元素。如果没有重复元素，则返回“此处没有重复元素！”。

当你看到这样的提示时，可能会因为其中提到的最小索引而感到有些困惑，但实际上，问题的本质非常简单。本质上，题目要求的是遍历数组，找到第一个重复元素——这就是要返回的元素！用最小索引来描述它只是更专业的说法，因为第一个重复元素应该出现在数组中更靠前/更小的索引位置。

例如，我们使用以下整数数组：

数组中 2、3 和 4 都重复出现，但3是第一个出现在arr[4]索引处的重复项。这正是我们想要通过函数返回的那个元素！

现在，让我们深入探讨一下解决这个问题的思路。这才是问题的关键所在，甚至比解决方案本身更重要。

当我们遇到像这样的问题，即要求处理数组中的重复项，无论是查找重复项、删除重复项还是其他情况，我们都知道我们可能需要两样东西：

1. 遍历数组的循环。
2. 用于存储循环中要进行比较的值的数据结构。

这里的步骤是：我们知道需要检查给定数组的大部分（甚至可能全部）元素——因此需要使用 for 循环——并且需要一些东西来保存每个被检查的值，以便检查我们是否已经检查过它们。这是一种逻辑清晰的方法，会在大量与数组相关的面试题和算法题中出现，因此熟练掌握它非常重要。

我们可以使用各种数据结构来保存这些值，但如果考虑到运行时复杂度，在 JavaScript 的上下文中，我们应该将其限制为哈希表、Map或Set对象。

我们之所以在这里使用上述方法之一，是因为在每次循环中，我们都会将给定数组中的每个值与已遍历的元素集合进行比较——检查哈希表中的键或值是常数时间复杂度，而使用像 ` Array.includes()`这样的函数会在每次循环中增加一次嵌套迭代。在这种情况下，我们将使用 ` Set`对象，因为它非常适合我们的特定场景。

是时候开始编写解决方案的代码了！

首先，我们来声明一下函数：

 JavaScript
function firstDuplicate(arr) {

}

现在，让我们创建 Set 对象：

 JavaScript
function firstDuplicate(arr) {
   let elementSet = new Set();
}

此 Set 对象允许我们将给定数组中的每个元素存储为唯一值，并使用两个函数检查它是否已包含值：Set.add()和Set.has()。

现在，让我们来实现遍历给定数组的循环：

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {

    } 
}

最后，我们将加入算法的核心逻辑：

1. 我们将检查集合中是否已经包含我们当前循环中正在处理的元素——如果存在，那么我们就找到了第一个重复项！我们将返回该值，然后结束操作。
2. 在达到这个里程碑之前，我们需要一个“else”语句，用于判断该元素是否还在我们的集合中，在这种情况下，我们将它添加到集合中，然后继续处理数组中的下一个元素。

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    } 
}

最后一步：处理数组中不存在重复项的特殊情况！我们将在循环结束后添加这一步，假设循环已完成且未返回重复值：

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    }

    return "No duplicates here!";
}

大功告成！现在我们已经掌握了如何快速检查并返回 JavaScript 数组中的第一个重复元素，无论数组数据类型如何。这个函数可以返回整数数组、字符串数组或混合数组中的第一个重复元素。

感谢您抽出时间阅读这篇教程，希望您喜欢并对该算法背后的概念有了更深入的了解！我也会不断努力加深自己对相关概念的理解，敬请期待更多类似的博客文章。:)