LeetCode：“Contains Duplicate”问题

Source: Dev.to

Problem Statement

“这个列表中是否有相同的数字出现了不止一次？”

大家都能理解的例子：

• [3, 7, 1, 9] → false
• [3, 7, 3, 9] → true
• [5] → false
• [8, 8] → true
• [] → false

我们需要一种可靠的方法来检测是否有数字出现多次。

Naïve Human Approach

想象列表 [4, 1, 7, 2, 9, 4, 8]。

1. 取 4 → 记住它
2. 取 1 → 新的 → 记住
3. 取 7 → 新的 → 记住
4. 取 2 → 新的 → 记住
5. 取 9 → 新的 → 记住
6. 取 4 → 重复！

算法：保持一个已见数字的记忆；如果遇到已经在记忆中的数字，就停止。

Naïve Python Implementation

def has_duplicate(nums):
    seen = []                # empty list = our memory

    for num in nums:         # look at each number one by one
        if num in seen:      # is it already in memory?
            return True      # yes → duplicate found
        seen.append(num)     # no → remember it

    return False             # no duplicates

Mental Run

输入：[4, 1, 7, 4] → 返回 True。

Complexity Issue

在列表上执行 num in seen 会遍历每个元素 → O(n) 的检查时间。
在对 n 个元素的循环中，总时间变为 O(n²)，这对大规模输入（例如 100,000 个元素）来说是不可接受的。

Optimized Solution with a Set

Python 的 set 提供近乎常数时间的成员测试（哈希表查找）。

def has_duplicate(nums):
    seen = set()             # fast lookup structure

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

现在算法的运行时间是 O(n)，额外空间也是 O(n)。

Full LeetCode‑style Class

class Solution:
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

# Simple test
s = Solution()
nums = [1, 0, 2, 5, 8, 9, 1]
result = s.containsDuplicate(nums)
print(result)   # True

运行代码即可确认预期输出。

Takeaways

• 选择合适的数据结构（列表 vs. 集合）会显著影响性能。
• 理解时间复杂度 能帮助你编写可扩展的解决方案。
• 将人类逻辑转化为高效的机器逻辑是算法问题求解的核心技能。

这些经验同样适用于 LeetCode 之外的场景：

• 设计 API
• 优化后端系统
• 处理大规模数据集
• 防止性能瓶颈

---

本周我专注于哈希表和字符串。为学习干杯！