LeetCode 219 & 220
上个问题我可能没表达清楚219 list替换Set
这里重新提问 同时219和220 两道题
LeetCode 219
这个问题 课程代码：
public static boolean containsNearbyDuplicate2(int[] nums, int k) {
//遍历nums中范围的值 这里用list 删除元素会错乱
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (set.contains(num)) {
return true;
}
set.add(num);
if (set.size() == k + 1) {
set.remove(nums[i - k]);
}
}
老师 我用list这个解法就是错的，我debug打印几次list发现 list.remove 当是Integer时 集合List他不知道时删除元素还是删除索引，所以会错乱，但是我这里还是有点怀疑，list顺序添加 可以顺序取出的吧？ 这个问题不能用list的原因是因为 remove这个方法的原因吗？
LeetCode 220
课程解法：
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length == 0)
return false;
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
long num = nums[i];
//num-t<= x <=num+t 查看是否存在这个x 找到大于 num-t的最小值 同时 这个值在[num-t,num+t]这个范围内就是成功的
Long ceiling = set.ceiling((long)num - t);
if (ceiling != null && ceiling <=(long) num + t)
return true;
set.add(num);
if (set.size() == k + 1) {
set.remove((long)nums[i - k]);
}
}
return false;
}
这里有1个问题：
对于k 我们用Set存 如果遇到重复元素 那么Set.size()>=k ，按照思想这个是一定的。但是看leetcode说根据我们的判断遇到重复元素会直接true，这是为什么，我们找到合适的例子，辛苦老师帮我解释下，最好能有个例子，我动笔试试
辛苦老师！
正在回答
2回答
在之前的问题里已经回复你里：set.remove(x) 的意思是从 set 中删除掉 x 这个元素；但是 list.remove(x) 的意思是删除掉 x 索引所在的元素。二者的参数意思是不一样的。
所以，如果 set 是一个 list 的话，set.remove(nums[i - k]); 的意思，不是从 这个 list 里删除 nums[i - k] 这个元素，而是把 nums[i - k] 看做一个索引，删除掉在 nums[i - k] 这个索引位置的元素。
比如对 [4, 3, 2, 1, 0] 这个数组，如果你想删除掉 4，应该调用 list.remove(0)，而不是 list.remove(4)。如果调用 list.remove(4)，最后删掉的是 0。因为 0 在索引 4 的位置；4 在索引 0 的位置。
对于这个问题，其实你每次删除第一个元素就好了。使用 LinkedList 或者 ArrayList，只需要这么写，就是正确的：
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
//遍历nums中范围的值 这里用list 删除元素会错乱
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (list.contains(num)) {
return true;
}
list.add(num);
if (list.size() == k + 1) {
list.remove(0); // 删除掉最早的元素
}
}
return false;
}
}
但是，这么做会超时，这是因为 list.contains(num) 此时是 O(n) 的，整个算法的时间复杂度是 O(n^2) 的。
继续加油！：）
