LeetCode #219 Contains Duplicate II

Easy

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

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

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

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

Solution

Complexity

It takes O(n) time to iterate nums if n denotes to counts of numbers in nums. In each iteration, search an insert operations of hash map take O(1)/O(logn) time in average/worst cases. Thus, time complexity will be O(n)/O(nlogn) in average/worst cases.

It’s trivial that space complexity is O(n)