217. Contains Duplicate

LeetCode 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], k = 3
Output: true

Constraints:

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

Tags

Array, Hash Table

Solution

A simple hash table application. We can use type map[int]struct{} to squeeze the space overhead.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func containsDuplicate(nums []int) bool {
	m := map[int]struct{}{}
	for _, num := range nums {
		if _, ok := m[num]; ok {
			return true
		}
		m[num] = struct{}{}
	}
	return false
}