[LeetCode] 219. Contains Duplicate II

轉自LeetCode

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= 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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

<Solution>

這題是 217. Contains Duplicate 的衍生題

這次多了一個條件是，相同兩個數字所在的 index 的絕對差值，必須小於等於 k

解題想法是

• 一樣使用 hash set 來記錄每個 index 所在的值

• 把和目前的 index 的差距超過 k 的值，從 hash set 裡面拿掉。這樣檢查的時候，就能確保 index 的絕對差是小於等於 k 的

code 如下

C++

	class Solution {
	public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
	unordered_set<int> table;
	const int len = nums.size();
	for(int i = 0; i < len; ++i) {
	if(i > k) {
	table.erase(nums[i-k-1]);
	}
	if(table.count(nums[i])) {
	return true;
	}
	table.insert(nums[i]);
	}
	return false;
	}
	};

view raw checkDuplicates_2.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean containsNearbyDuplicate(int[] nums, int k) {
	HashSet<Integer> table = new HashSet<>();
	for(int i = 0; i < nums.length; ++i) {
	if(i > k) {
	table.remove(nums[i-k-1]);
	}
	if(table.contains(nums[i])) {
	return true;
	}
	table.add(nums[i]);
	}
	return false;
	}
	}

view raw checkDuplicates_2.java hosted with ❤ by GitHub

另一個解法是用 sliding window 的概念

當 right 指標不斷向右移的時候，如果發現有重複的數字出現

檢查是否符合條件，是的話就回傳 true

不符合條件，更新 map，繼續找下去

kotlin

	class Solution {
	fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
	val map = mutableMapOf<Int,Int>()
	var left = -1
	for(right in nums.indices) {
	left = map[nums[right]] ?: -1
	if(left > -1 && right - left <= k) {
	return true
	}
	map[nums[right]] = right
	}
	return false
	}
	}

view raw contains_duplicate_II.kt hosted with ❤ by GitHub