Given an integer array nums, determine if it contains any duplicates.

Return true if any value appears at least twice in the array, and return false if every element is distinct.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Example:

Input: nums = [1,2,3,1]
Output: true
Explanation: The number '1' appears twice.

Solution

Approach:

The most efficient way to check for duplicates is using a hash set (also known as a set in Python, HashSet in Java, unordered_set in C++).

  • Initialize a hash set: This set will store all unique numbers encountered so far.
  • Iterate through the array: For each number num in nums:
    • Check for existence: If num is already present in the hash set, it means we've found a duplicate. Immediately return true.
    • Add to set: If num is not in the hash set, add it to the set to mark it as seen.
  • No duplicates found: If the loop completes without returning true, it means no duplicates were found, so return false.

Python Solution:

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set() # Initialize a hash set to store seen numbers
        for num in nums:
            if num in seen:
                # If the number is already in the set, it's a duplicate
                return True
            seen.add(num) # Add the current number to the set
        # If the loop finishes, no duplicates were found
        return False