219. Contains Duplicate II
https://leetcode.com/problems/contains-duplicate-ii/
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
Intuition
To achieve linear O(N) complexity, scan from L to R.. do not sort
Save elements in a set
if set.size() > k
remove nums[i - k - 1]
if set.contains(nums[i])
return true
set.add(nums[i])
---
Time - O(N)
Space - O(K)
---
Related problems
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public boolean containsNearbyDuplicate(int[] nums, int k) { | |
| Set<Integer> set = new HashSet<Integer>(); | |
| for (int i = 0; i < nums.length; i++) { | |
| if (set.size() > k) { | |
| set.remove(nums[i - k - 1]); | |
| } | |
| if (set.contains(nums[i])) { | |
| return true; | |
| } | |
| set.add(nums[i]); | |
| } | |
| return false; | |
| } | |
| } |
