220. Contains Duplicate III

220. 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.

思路： 维持一个长度为k的window, 每次检查新的值是否与原来窗口中的所有值的差值有小于等于t的. 如果用两个for循环会超时O(nk). 使用treeset( backed by binary search tree) 的subSet函数,可以快速搜索. 复杂度为O(n logk)。

class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(k < 1 || t < 0 || nums == null || nums.length < 2) return false; SortedSet set = new TreeSet(); for(int j = 0; j < nums.length; j++) { SortedSet subSet = set.subSet((long)nums[j] - t, (long)nums[j] + t + 1); if(!subSet.isEmpty()) return true; if(j >= k) { set.remove((long)nums[j - k]); } set.add((long)nums[j]); } return false; }}

class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { TreeMap map = new TreeMap<>(); int j=0; for(int i=0;ik) { if(map.get(Long.valueOf(nums[j]))==j) map.remove(Long.valueOf(nums[j])); j++; } if(map.ceilingKey(Long.valueOf(nums[i])-t)!=null && map.ceilingKey(Long.valueOf(nums[i])-t)<=Long.valueOf(nums[i])+t) return true; map.put(Long.valueOf(nums[i]), i); } return false; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。