Contains Duplicate
EasyThe problem
Given a list of numbers, return true if any number appears more than once, and false if every number is different.
- Example 1Input: nums = [1, 2, 3, 1]Output: true
The number 1 appears twice.
- Example 2Input: nums = [4, 5, 6, 7]Output: false
Every number is different.
Limits
- 1 ≤ nums.length ≤ 100,000
- -1,000,000,000 ≤ nums[i] ≤ 1,000,000,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
While scanning, what question do you keep asking about the current number?
The idea
Keep a set of numbers seen so far. If the current number is already in the set, return true; otherwise add it.
Target: O(n) time, O(n) space
Go function shape
func containsDuplicate(nums []int) boolReference solution
Tested with go test. Try it yourself first, then compare.
// ContainsDuplicate: does any value appear at least twice?
// A map used as a set: struct{} stores nothing but membership.
func ContainsDuplicate(nums []int) bool {
seen := map[int]struct{}{}
for _, v := range nums {
if _, ok := seen[v]; ok {
return true
}
seen[v] = struct{}{}
}
return false
}