💬 Discord
Sign In
NeetCode #2LC-217EasyArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#2 · #217 · Contains Duplicate(存在重复元素)

📌 Problem Statement & Constraints

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct. Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Walk the array once and keep a hash set of values already seen.
  2. For each element, test membership first: if it is already in the set, we have a duplicate, so return true immediately.
  3. Otherwise add it and continue. If the loop finishes, every value was unique, so return false.
  4. The early return is what keeps the average case cheap; there is no need to finish the scan once a duplicate is found.

💻 Benchmark Python3 Implementation

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for x in nums:
            if x in seen:          # second sighting -> duplicate
                return True
            seen.add(x)
        return False


# One-liner equivalent: build the set, compare its size
class Solution2:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) expected time: one pass, with O(1) average-cost hash lookups and insertions. The theoretical worst case is O(n^2) if the hash function degenerates, which Python's randomized string/int hashing makes practically unreachable.
💾 Space Complexity
O(n) for the set in the worst case (all elements distinct). A sort-based solution would use O(1) extra space but cost O(n log n) time, so the set wins on time and loses on space.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting first: nums.sort() then comparing neighbours is O(n log n) and mutates the input. Correct, but strictly worse than the hash-set pass.
  • Using a list instead of a set for seen: membership becomes O(n), turning the whole algorithm into O(n^2).
  • Thinking the set always needs O(n) memory: it does in the worst case, but the early return means a duplicate-heavy input stops almost immediately.
  • Overflow worries: values reach 1e9, but that is irrelevant for hashing; no arithmetic is performed.