217. Contains Duplicate

Description of the Problem

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

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints:

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

Solution

Code (Java)

// import java.util.HashSet;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet <Integer> set = new HashSet();
        for (int n : nums){
            if (!set.add(n))
                return true;
        }
        return false;
    }
}

Code(Rust)

use std::collections::HashSet;

impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {

        let mut set : HashSet<i32> = HashSet::new();
        for n in nums {
            if !set.insert(n) {
                return true;
            }
        }
        return false;
    }
}

Complexity

n is the number of elements in the array

Time complexity:

\( T(n) = O(n) \)

Auxiliary Space:

\( S(n) = O(n) \)
- For HashMap

Leetbook