LeetCode - Easy - 219. Contains Duplicate II

女爷i 2022-12-31 05:29 151阅读 0赞

## Topic ##

*  Array
 *  Hash Table
 *  Sliding Window

## Description ##

[https://leetcode.com/problems/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

## Analysis ##

方法一：使用HashMap。

方法二：比方法一精简些。

方法三：使用HashSet作移动窗口。

It iterates over the array using a **sliding window**. The front of the window is at `i`, the rear of the window is `k` steps back. The elements within that window are maintained using a `Set`. While adding new element to the set, if `add()` returns `false`, it means the element already exists in the set. At that point, we return `true`. If the control reaches out of for loop, it means that inner `return true` never executed, meaning no such duplicate element was found.

## Submission ##

import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    
    public class ContainsDuplicateII { 
    
    	// 方法一：我写的，用哈希表实现
    	public boolean containsNearbyDuplicate1(int[] nums, int k) { 
    		if (nums == null || nums.length == 0 || k < 1)
    			return false;
    
    		Map<Integer, Integer> cache = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) { 
    			Integer existedIndex = cache.get(nums[i]);
    			if (existedIndex != null && Math.abs(existedIndex - i) <= k)
    				return true;
    			cache.put(nums[i], i);
    		}
    
    		return false;
    	}
    
    	// 方法二：比方法一更加简单
    	public boolean containsNearbyDuplicate2(int[] nums, int k) { 
    		Map<Integer, Integer> indices = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) { 
    			Integer lastIndex = indices.put(nums[i], i);
    			if (lastIndex != null && (i - lastIndex) <= k)
    				return true;
    		}
    		return false;
    	}
    
    	// 方法三：用HashSet实现
    	public boolean containsNearbyDuplicate3(int[] nums, int k) { 
    		Set<Integer> set = new HashSet<Integer>();
    		for (int i = 0; i < nums.length; i++) { 
    			if (i > k)
    				set.remove(nums[i - k - 1]);
    			if (!set.add(nums[i]))
    				return true;
    		}
    		return false;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class ContainsDuplicateIITest { 
    
    	@Test
    	public void test() { 
    		ContainsDuplicateII obj = new ContainsDuplicateII();
    
    		int[][] array1 = { { 1,2,3,1},{ 3}},
    				array2 = { { 1,0,1,1},{ 1}},
    				array3 = { { 1,2,3,1,2,3},{ 2}};
    		
    		assertTrue(obj.containsNearbyDuplicate1(array1[0], array1[1][0]));
    		assertTrue(obj.containsNearbyDuplicate1(array2[0], array2[1][0]));
    		assertFalse(obj.containsNearbyDuplicate1(array3[0], array3[1][0]));
    		
    		assertTrue(obj.containsNearbyDuplicate2(array1[0], array1[1][0]));
    		assertTrue(obj.containsNearbyDuplicate2(array2[0], array2[1][0]));
    		assertFalse(obj.containsNearbyDuplicate2(array3[0], array3[1][0]));
    		
    		assertTrue(obj.containsNearbyDuplicate3(array1[0], array1[1][0]));
    		assertTrue(obj.containsNearbyDuplicate3(array2[0], array2[1][0]));
    		assertFalse(obj.containsNearbyDuplicate3(array3[0], array3[1][0]));
    	}
    }

[https_leetcode.com_problems_contains-duplicate-ii]: https://leetcode.com/problems/contains-duplicate-ii/