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

说人话：

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。

如果存在则返回 true，不存在返回 false。

示例1：

示例2：

[法1] 暴力法

思路

暴力法的思路就是双层遍历数据 nums，然后检查是否有满足 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 的情况，如果有就返回 true，如果遍历完数组还没有，就返回 false。

代码

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

        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
              	//注意这里为了避免整数 int 溢出，需要转换为 long 类型
                if(Math.abs((long)nums[i]-(long)nums[j])<=(long)t && j-i<=k){
                    return true;
                }
            }
        }
        return false;
    }
}

提交结果

代码分析

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

改进思路

我们需要将时间复杂度 O(n²) 降为 O(n) 或者 O(nlogn)，也就是希望可以扫描一遍数组便解决问题。从题目要求的两个条件来看：

• i 和 j 的差的绝对值小于等于 ķ 的情况
• 滑动窗口
• nums [i] 和 nums [j] 的差的绝对值小于等于 t
  • 利用查找表找是否有满足 v-t <= v <= v+t 的元素，这样就需要具有顺序性的查找表，那么就可以用 Tree，又由于数据的不可重复性（i != j），那么就可以用 Set，综合起来我们可以用 TreeSet 来辅助解决本问题。

[法2] 查找表

思路

• 遍历数组 nums[i]，边遍历边将元素放到 TreeSet 中
• 遍历到 nums[i] 的时候，检查 TreeSet 中是否存在 v-t <= v <= v+t 的元素
  • v >= v-t 可以用 treeSet.ceiling(v-t) 来判断是否存在（ ceiling(v-t) 是找出 TreeSet 中大于或等于 v-t 的最小元素）
• 如果存在，则返回 true
• 如果不存在，则将 nums[i] 放入 TreeSet 中
• 放入 nums[i] 后检查 TreeSet 中元素个数是否超过 k
• 如果超过 k，就删除窗口左边的第一个元素 nums[i-k]
• 直至遍历完整个数组

代码

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

        //为了防止溢出，需要用 long 类型
        TreeSet<Long> treeSet = new TreeSet<>();

        //set中元素个数
        int count = 0;

        //遍历数组
        for(int i=0;i<nums.length;i++){
            //判断是否存在元素 x >= nums[i]-t 
            Long number = treeSet.ceiling((long)nums[i]-(long)t);
            //如果存在，还需要这个元素 x <= nums[i]+t
            if(number != null && number <= (long)nums[i]+(long)t){
                return true;
            }else{
                //不存在就继续往 TreeSet 中扔元素
                treeSet.add((long)nums[i]);
                count ++;

                //检查是否越出窗口
                if(count > k){
                    treeSet.remove((long)nums[i-k]);
                    count --;
                }
            }

        }
        return false;
    }
}

提交结果

代码分析

• 时间复杂度：时间复杂度：因为 TreeSet 每一个 add 操作的时间复杂度是 O(logn)，故整体时间复杂度是 O(nlogn)
• 空间复杂度：O(k)