220. Contains Duplicate III

古城微笑少年丶 2022-05-29 03:27 147阅读 0赞

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.

这题描述的很清晰，integer数组题目给了一个k和t，要求判断在数组中是否存在两下标分别为i和j的数，其中要求t >= | nums\[j\] - nums\[i\] | 并且k >= | j - i |

这个就和TCP里的滑动窗口类似，这个窗口大小一定，就在数组里滑动的寻找合适的

正如题所要求的 t >= numsj - numsi 即 t + numsi >= numsj

具体解释请看代码中的注释

public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
    		// 用treeset来存储，其本质是BST
    		TreeSet<Long> ts = new TreeSet<>();
    		// ceiling 天花板 之所以用Long类型存储是为了数字中出现接近integer的maxValue而溢出的情况
    		Long ceilling;
    		
    		for (int i=0; i<nums.length; i++) {
    			if (t < 0 || k < 0)
    				return false;
    			// t >= numsi - numsj 即 numsj >= numsi - t 判断set中是否存在比numsi - t更大的数
    			ceilling = ts.ceiling((long)nums[i] - t); // the least element , greater than or equal to the given element
    			
    			// 如果set中无比符合要求的数 那从if中出去，讲本次迭代到的numsi添加到数组中
    			// 如果set中存在大于numsi - t的数字 再判断是否这个数字和当前迭代到的数字之差是否小于等于t
    			if (ceilling != null && Math.abs(nums[i] - ceilling) <= t)
    				return true;
    			
    			ts.add((long) nums[i]);
    			
    			// 如果i大过k了 为了满足小于等于k的条件 我们得把窗口长度限制在k以内 所以超过k的 并且不符合要求的都remove掉
    			if (i >= k) 
    				ts.remove((long)nums[i-k]);
    		}
    		return false;
        }