- 19.3%

https://leetcode.com/problems/contains-duplicate-iii/?tab=Description

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.

需要思考

方法一：

因为需要有序，所以使用的set，set也有lower_bound相关函数

学习set，排序的set，学习low_bound函数使用

比较直接，使用了lower_bound, upper_bound

如果要存在，肯定在两者之间

我的代码实现：

1 | class Solution { |

下面的算法有一定的公式推导，但是也比较简单，原理是一致的。

https://discuss.leetcode.com/topic/18453/c-using-set-less-10-lines-with-simple-explanation

C++ using set (less 10 lines), with simple explanation.

1 | bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { |

https://discuss.leetcode.com/topic/15468/i-finally-got-ac-in-c

I finally got AC in C++

Using a set container to keep the k+1-length array,which all elements are distinct.Before the container’s size reached k+1, we just find the first element that is not less than [nums[i]-t] and judge the element’s value whether it is less than [nums[i]+t]. Starting to move forward by erasing the head and adding element at the backend after the container’s size reached k+1. The existence of the first element ,which is not less than [nums[i]-t] and less than [nums[i]+t], is the prerequisite of existing other eligible elements.

1 | bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) |

https://discuss.leetcode.com/topic/15172/accept-c-solution

Accept C++ Solution

My idea is to preserve a sliding window containing nearest k numbers, and check if next number collides to the numbers in the window.

1 | class Solution { |

#### python

The idea is like the bucket sort algorithm. Suppose we have consecutive buckets covering the range of nums with each bucket a width of (t+1). If there are two item with difference <= t, one of the two will happen:

1 | (1) the two in the same bucket |

For detailed explanation see my blog here

Python

1 | def containsNearbyAlmostDuplicate(self, nums, k, t): |

Java

1 | private long getID(long i, long w) { |

https://discuss.leetcode.com/topic/19991/o-n-python-using-buckets-with-explanation-10-lines

O(n) Python using buckets with explanation, 10 lines.

1 | def containsNearbyAlmostDuplicate(self, nums, k, t): |

https://discuss.leetcode.com/topic/15190/python-ordereddict

Python OrderedDict

1 | class Solution: |

#### java

https://discuss.leetcode.com/topic/15199/ac-o-n-solution-in-java-using-buckets-with-explanation

AC O(N) solution in Java using buckets with explanation

As a followup question, it naturally also requires maintaining a window of size k. When t == 0, it reduces to the previous question so we just reuse the solution.

Since there is now a constraint on the range of the values of the elements to be considered duplicates, it reminds us of doing a range check which is implemented in tree data structure and would take O(LogN) if a balanced tree structure is used, or doing a bucket check which is constant time. We shall just discuss the idea using bucket here.

Bucketing means we map a range of values to the a bucket. For example, if the bucket size is 3, we consider 0, 1, 2 all map to the same bucket. However, if t == 3, (0, 3) is a considered duplicates but does not map to the same bucket. This is fine since we are checking the buckets immediately before and after as well. So, as a rule of thumb, just make sure the size of the bucket is reasonable such that elements having the same bucket is immediately considered duplicates or duplicates must lie within adjacent buckets. So this actually gives us a range of possible bucket size, i.e. t and t + 1. We just choose it to be t and a bucket mapping to be num / t.

Another complication is that negative ints are allowed. A simple num / t just shrinks everything towards 0. Therefore, we can just reposition every element to start from Integer.MIN_VALUE.

1 | public class Solution { |

Edits:

Actually, we can use t + 1 as the bucket size to get rid of the case when t == 0. It simplifies the code. The above code is therefore the updated version.

https://discuss.leetcode.com/topic/15191/java-o-n-lg-k-solution

Java O(N lg K) solution

This problem requires to maintain a window of size k of the previous values that can be queried for value ranges. The best data structure to do that is Binary Search Tree. As a result maintaining the tree of size k will result in time complexity O(N lg K). In order to check if there exists any value of range abs(nums[i] - nums[j]) to simple queries can be executed both of time complexity O(lg K)

Here is the whole solution using TreeMap.

1 | public class Solution { |