219. Contains Duplicate

yPhantom 2019年10月14日 27次浏览

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Solution

题意让找以i为中心,左右两边最长相距k为边界的一个范围内,是否存在与nums[i]相等的值。

上来先试了下O(n2)的暴力遍历法,发现果然Time Limit Exceed了。

对于这种有左右范围的题目,可以考虑窗口法:

以i-k到i这一段作为窗口的宽,每次窗口向右移动1单位,得到O(n)的算法:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || k < 1) {
            return false;
        }
        Set<Integer> set = new HashSet<>(); // 利用set的add方法来判断是否有相同值
        for(int i = 0; i < nums.length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]); // 移除窗口的边界的前一个值。保证窗口大小
            }
            if(!set.add(nums[i])) {
                return true;
            }
            
        }
        return false;
    }
}

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.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution

接ii题,该题的题意是让判断是否存在下标左右范围为k,值的上下范围为t的情况。通过前一题我们已经知道,一般下标范围题我们可以用窗口法,而对于值的范围题,我们用上桶排序。

因此这一题结合桶排序和窗口法。

我们设置的桶的大小为t + 1(如果设置t=0的话,会导致除数为0,并且每个的大小单位为1),求得每个数对应的桶的序号,有两种情况:

  • map中已经包含了该序号,道理同前一题,直接返回true。
  • 前一个桶或者后一个桶中存在与所求值的绝对值小于t的值,返回true。

并且由于支持正负数,因此减去Integer.MIN_VALUE这样就不会逼近0。得到算法:

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || k < 1 || t < 0) {
            return false;
        }
        Map<Long, Long> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            long value = (long)nums[i] - Integer.MIN_VALUE;
            long bucket = value / ((long)t + 1);
            if (map.containsKey(bucket)
                 || (map.containsKey(bucket - 1) && value - map.get(bucket - 1) <= t)
                    || (map.containsKey(bucket + 1) && map.get(bucket + 1) - value <= t)) {
                return true;
            }
            if (map.entrySet().size() >= k) {
                long lastBucket = ((long)nums[i - k] - Integer.MIN_VALUE) / ((long)t + 1);
                map.remove(lastBucket);
            }
            map.put(bucket, value);
        }
        return false;
    }
}

注意,这种方法的窗口的左边界的最后一个桶的下标的求法。