217. Contains Duplicate
## description
## 217. Contains Duplicate
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
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
- –1 <= nums.length <= 105
- –-109 <= nums[i] <= 109
Constraints:
## notes
### Intuition
To detect duplicates, we need to remember which numbers we've seen. A hashmap provides O(1) lookup to check if a number has appeared before.
### Implementation
Iterate through the array. For each number, check if it's already in the hashmap—if so, we found a duplicate, return True. Otherwise, add the number to the map and continue. If the loop completes, no duplicates exist, return False.
### Edge-cases
An empty array or single-element array has no duplicates by definition. The algorithm handles these naturally.
- –Time: O(n) — single pass with O(1) lookups
- –Space: O(n) — hashmap stores up to n elements
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def containsDuplicate(self, nums: List[int]) -> bool:
5 map = {}
6 for num in nums:
7 if num in map:
8 return True
9 map[num] = True
10
11 return False
12
13
14
15
16if __name__ == "__main__":
17 # Include one-off tests here or debugging logic that can be run by running this file
18 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
19 solution = Solution()
20