# 217. Contains Duplicate

## Description

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 <= 105
• -109 <= nums[i] <= 109

## Solutions

Solution 1: Sorting

First, we sort the array nums.

Then, we traverse the array. If there are two adjacent elements that are the same, it means that there are duplicate elements in the array, and we directly return true.

Otherwise, when the traversal ends, we return false.

The time complexity is $O(n \times \log n)$, where $n$ is the length of the array nums.

Solution 2: Hash Table

We traverse the array and record the elements that have appeared in the hash table $s$. If an element appears for the second time, it means that there are duplicate elements in the array, and we directly return true.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array nums.

• class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int num : nums) {
return true;
}
}
return false;
}
}

• class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
return s.size() < nums.size();
}
};

• class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)

############

class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
nums.sort()
for i in range(0, len(nums) - 1):
if nums[i] == nums[i + 1]:
return True
return False


• func containsDuplicate(nums []int) bool {
s := map[int]bool{}
for _, v := range nums {
if s[v] {
return true
}
s[v] = true
}
return false
}

• function containsDuplicate(nums: number[]): boolean {
return new Set<number>(nums).size !== nums.length;
}


• /**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function (nums) {
return new Set(nums).size !== nums.length;
};


• class Solution {
/**
* @param Integer[] $nums * @return Boolean */ function containsDuplicate($nums) {
$numsUnique = array_unique($nums);
return count($nums) != count($numsUnique);
}
}

• public class Solution {
public bool ContainsDuplicate(int[] nums) {
return nums.Distinct().Count() < nums.Length;
}
}

• use std::collections::HashSet;
impl Solution {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
nums.iter().collect::<HashSet<&i32>>().len() != nums.len()
}
}