题目：Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Input:
- 数组 :: int[]
Output:
- 数组是否有重复的数 :: boolean
Intuition:
最最直接的想法是用set，因为这是set最最明显的性质了。如果某个数无法加入set中那么就是duplicates了。注意set里的search与insert都是constant time。
Code:
TC: O(n) SC: O(n)
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n: nums){
if (set.contaiAns(n)){
return true;
}
set.add(n);
}
return false;
}
题目：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.
Input:
- 数组 :: int[]
- 两duplicates的index差最多为k :: int
Output:
- 数组是否有重复的数 :: boolean
Intuition:
沿用之前题目的使用set的思想。但此时，我们不仅要往set里放值，而且还要往外拿。为什么？因为当set里的值的index与当前值的index大于k时，他对于解就没有价值了，那么干啥还要留着他捏？所以我们保持一个大小为k的Hashset就够了。另外remove() 的时间复杂度也是constant的。
Code:
TC:O(n) SC: O(min(n， k))
public boolean ContainsDuplicateII(int[] nums, int k){
Set<Integer> set = new HashSet<>();
for (int n: nums) {
if (set.contains(n)){
return true;
}
set.add(n);
//Sliding window
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
题目：Contains Duplicate III
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.
Input:
- 数组 :: int[]
- 两duplicates的index差最多为k :: int
- 两duplicates的值差最多为t :: int
Output:
- 数组是否有重复的数 :: boolean
Intuition:
这回不仅在index做了限制，连值上也做了限制。那最直接的想法就是在确保一个条件满足的情况下，去检查另一个条件是否满足。
如果用treeset的话，因为已经是sorted的情况，那么就检查某一个值的相邻最近的值(ceiling和floor)满不满足值差最多为t的条件。注意Treeset的sort复杂度是nlg(n), 增删改查的复杂度是lg(n).同样的使用sliding window的思路。
Code
TC:O(nlog(min(n,k))) SC:O(nlog(min(n,k)))
public boolean ContainsDuplicatesIII(int[]nums, int k, int t){
Set<Integer> treeset = new TreeSet<>();
for (int i = 0; i < nums.length; i++){
//check ceiling
int ceiling = set.ceiling(nums[i]);
if (ceiling != null && ceiling - t <= nums[i]){
return true;
}
//check floor
int floor = set.floor(nums[i]);
if(floor != null && floor + t >= nums[i]){
return true
}
set.add(nums[i]);
//sliding window
if(set.size() > k){
set.remove(nums[i - k]);
}
}
return false;
}
有没有O(n)的解法呢？想想看在O(n)内可以完成sort的算法是什么？桶排序对不对？当然我们这题没有必要完全sort整个数组，只不过利用了每个桶中数值都在设定范围内这一特性。
我们设桶的size为t，那么可以再k范围内扔进一个桶的数一定能满足条件。另外需要考虑的两个地方就是这个桶两边的桶，也可能还有值差小于t的情况，要分别检查下~
要注意的tricky的地方在于，对于负数，桶的选择要先加1除以桶的size再减一。为什么这么做呢？ 举个🌰，在Java里，-3/5是0，而它应该是在index为-1的桶中。那么就需要这么做修正下。当然如果用python等别的语言不存在这个顾虑就不用考虑这个情况了。
Code
TC:O(nlog(min(n,k))) SC:O(nlog(min(n,k)))
public boolean ContainsDuplicatesIII(int[] nums, int k, int t){
Map<Long, Long> map = new HashMap<>();
int size = t + 1 // in case t == 0, we need to add extra 1
for (int i = 0; i< nums.length; i++){
int idx = getIdx(nums[i], size);
//duplicates are in the same bucket
if(map.containsKey(idx)){
return true;
}
//duplicates are in neighbour buckets
if (map.containsKey(idx + 1) && Math.abs(nums[i] - map.get(idx + 1))){
return ture;
}
if (map.containsKey(idx - 1) && Math.abs(nums[i] - map.get(idx - 1))){
return ture;
}
map.put(idx, (long)(nums[i]));
if(map.size() > k){
map.remove(getIdx(nums[i - k], size));
}
}
}
public int getIdx(int x, int size){
if(x < 0){
return (x - 1) / size + 1;
}
return x / size;
}
Reference
https://leetcode.com/problems/contains-duplicate/
https://leetcode.com/problems/contains-duplicate-ii/solution/
https://leetcode.com/problems/contains-duplicate-iii/solution/
