[刷题防痴呆] 0220 - 存在重复元素III (Contai

题目地址

https://leetcode.com/problems/contains-duplicate-iii/description/

题目描述

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

思路

维护一个sliding window. 来不停判断 abs diff.

关键点

• for 循环.
• 从0开始. i之后的每个元素判断 abs diff <= t.
• 判断的跳出条件为, nums.length, 或到i+k.
• 注意, 外层i循环到nums.length - 1.
• O(n2)的算法会TLE, 使用treeset来维护k大小的window, 如果里面存在 num - left <= t或者right - num <= t则有解.时间复杂度为O(nlogk).
• treeset方法, lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null.

代码

• 语言支持：Java

// O(n2) TLE
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 <= i + k && j < nums.length; j++) {
                if (Math.abs((long)nums[i] - (long)nums[j]) <= t) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

// 红黑树做法 TreeSet O(nlogk)
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long num = nums[i] * 1L;
            Long left = treeSet.floor(num);
            Long right = treeSet.ceiling(num);
            if (left != null && num - left <= t) {
                return true;
            }
            if (right != null && right - num <= t) {
                return true;
            }
            treeSet.add(num);
            if (i >= k) {
                treeSet.remove(nums[i - k] * 1L);
            }
        }

        return false;
    }
}