Java for LeetCode 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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

解题思路：

暴力枚举会LTE，解题思路是用sortedSet来解决，sortedSet可以返回一个在某个范围的subSet，同时判断这个subSet是否为空即可解决，主要，本题需要使用long类型！

JAVA实现如下：

import java.util.*;

public class Solution {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if(nums==null || nums.length<2||k<1 || t<0)

        	return false;

        SortedSet<Long> set = new TreeSet<Long>();

        for(int j=0; j<nums.length; j++) {

            SortedSet<Long> 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;

    }

}

巴特西

Java for LeetCode 220 Contains Duplicate III

最新文章

热门文章