[LeetCode] 220. Contains Duplicate III

轉自LeetCode

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

<Solution>
Contains Duplicate II 的再度衍生

這次要找的不是數值相同而已，而是絕對數值差在 t 以內都可以

思考方向

• 運用 bucket 的概念來檢查是否差值在 t 以內。例如 bucket 的大小為 3，則 [0,3] 這個 bucket 可以包涵 0,1,2，差值都是在 3 以內

• 在檢查的時候，也要檢查前後的 bucket。例如 2 和 4 分別在 [0,3] 和 [3,6] 這兩個不同 bucket，可是他們差值依然小於 3

• 因為落在哪個 bucket 會使用除法，如果分子為負數的話，則全部都會落在第一個 bucket，所以先將每個數減掉 int 的最小值，來都變成正數

code 如下

C++

	class Solution {
	public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
	if (k < 1 || t < 0) {
	return false;
	}
	unordered_map<long, long> table;
	long mappedVal, bucket, lastBucket;
	const long bucketNum = (long)t+1; //>> use t+1 to avoid t = 0
	const int len = nums.size();
	for(int i = 0; i < len; ++i) {
	mappedVal = (long)nums[i] - INT_MIN;
	bucket = mappedVal / bucketNum;
	if(table.count(bucket)
	|| (table.count(bucket-1) && mappedVal - table[bucket-1] <= t)
	|| (table.count(bucket+1) && table[bucket+1] - mappedVal <= t)) {
	return true;
	}
	if(table.size() == k) {
	lastBucket = ((long) nums[i-k] - INT_MIN) / bucketNum;
	table.erase(lastBucket);
	}
	table[bucket] = mappedVal;
	}
	return false;
	}
	};

view raw checkDuplicates_3.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
	if(k < 1 || t < 0) {
	return false;
	}
	HashMap<Long, Long> map = new HashMap<>();
	long bucket, mappedVal;
	final long buckNum = (long) t + 1;
	for(int i = 0; i < nums.length; i++) {
	if(i > k) {
	bucket = ((long)nums[i-k-1] - Integer.MIN_VALUE) / buckNum;
	map.remove(bucket);
	}
	mappedVal = (long) nums[i] - Integer.MIN_VALUE;
	bucket = mappedVal / buckNum;
	if(map.containsKey(bucket)
	|| (map.containsKey(bucket+1) && map.get(bucket+1) - mappedVal <= t)
	|| (map.containsKey(bucket-1) && mappedVal - map.get(bucket-1) <= t)) {
	return true;
	}
	map.put(bucket, mappedVal);
	}
	return false;
	}
	}

view raw checkDuplicates_3.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun containsNearbyAlmostDuplicate(nums: IntArray, k: Int, t: Int): Boolean {
	val map = mutableMapOf<Long,Long>()
	val buckNum = t.toLong() + 1
	for(i in nums.indices) {
	if(i > k) {
	val bucket = (nums[i-k-1].toLong() - Int.MIN_VALUE) / buckNum
	map.remove(bucket)
	}
	val mappedValue = nums[i].toLong() - Int.MIN_VALUE
	val bucket = mappedValue / buckNum
	if(map.containsKey(bucket)
	|| (map.containsKey(bucket+1) && map[bucket+1]!! - mappedValue <= t)
	|| (map.containsKey(bucket-1) && mappedValue - map[bucket-1]!! <= t)
	) {
	return true
	}
	map[bucket] = mappedValue
	}
	return false
	}
	}

view raw contains_duplicate_III.kt hosted with ❤ by GitHub