Java solution using sliding window beating 100.00%


  • 0
    D
    public class Solution {
            class Pair{
    		long num;
    		int idx;
    		
    		public Pair(long num, int idx){
    			this.num = num;
    			this.idx = idx;
    		}
    	}
    	
    	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    		int n = nums.length;
                    if (n <= 1 || t <  0) return false;
    		Pair[] ps = new Pair[n];
    		for (int i = 0; i < nums.length; ++i) ps[i] = new Pair((long)nums[i], i);
    		
    		Arrays.sort(ps, new Comparator<Pair>() {
    			@Override
    			public int compare(Pair o1, Pair o2) {
    				return o1.num < o2.num ? -1 : 1;
    			}
    		});
    		
    		int lb = 0, rb = 0;
    		for (;;){
    			while (rb < n && ps[rb].num - ps[lb].num <= t){
    				if (rb != lb && Math.abs(ps[rb].idx - ps[lb].idx) <= k) return true;
    				rb++;
    			}
    			if (rb == n || ps[rb].num - ps[lb].num <= t) break;
    			lb++;
    		}
    		for (int i = lb; i < rb - 1; ++i)
    			if (Math.abs(ps[n-1].idx - ps[i].idx) <= k && ps[n-1].num - ps[i].num <= t) return true;
    		return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.