220. Contains Duplicate III

栏目: Java · 发布时间: 5年前

内容简介: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:Example 2:

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

难度:medium

题目:给定一整数数组,找出是否存在两个不同的索引i, j使其索引差的绝对值小于等于k, 值的差的绝对值小于等于t.

思路:

  1. 暴力破解,
  2. 使用滑动窗口和TreeSet是为了使得滑动窗口有序,TreeSet底层是二叉搜索树, 如果暴力破解时间复杂度为O(kn), 改用TreeSet使得搜索时间复杂度为O(log K), 故总的时间复杂度为O(nlog K)。

Runtime: 22 ms, faster than 70.38% of Java online submissions for Contains Duplicate III.

Memory Usage: 40.4 MB, less than 5.58% of Java online submissions for Contains Duplicate III.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums == null || nums.length < 2 || k < 1 || t < 0){
            return false;
        }
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!treeSet.subSet((long) nums[i] - t, true, (long) nums[i] + t, true).isEmpty()) {
                return true;
            }
            if (i >= k) {
                treeSet.remove((long) nums[i - k]);
            }
            treeSet.add((long) nums[i]);
        }
                    
        return false;
    }
}

Runtime: 987 ms, faster than 5.06% of Java online submissions for Contains Duplicate III.

Memory Usage: 38.8 MB, less than 56.75% of Java online submissions for Contains Duplicate III.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < Math.min(nums.length, i + k + 1); j++) {
                if (nums[i] > 0 && nums[j] < 0 || nums[i] < 0 && nums[j] > 0) {
                    if (Math.abs(nums[i]) - t > 0 
                        || Math.abs(nums[i]) - t + Math.abs(nums[j]) > 0) {
                        continue;
                    }
                }
                
                if (Math.abs(nums[i] - nums[j]) <= t) {
                    return true;
                }
            }
        }
                    
        return false;
    }
}

以上所述就是小编给大家介绍的《220. Contains Duplicate III》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

黑客大曝光

黑客大曝光

Joel Scambray、Vincent Liu、Caleb Sima / 姚军 / 机械工业出版社华章公司 / 2011-10 / 65.00元

在网络技术和电子商务飞速发展的今天,Web应用安全面临着前所未有的挑战。所有安全技术人员有必要掌握当今黑客们的武器和思维过程,保护Web应用免遭恶意攻击。本书由美国公认的安全专家和精神领袖打造,对上一版做了完全的更新,覆盖新的网络渗透方法和对策,介绍如何增强验证和授权、弥补Firefox和IE中的漏洞、加强对注入攻击的防御以及加固Web 2.0安全,还介绍了如何将安全技术整合在Web开发以及更广泛......一起来看看 《黑客大曝光》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试