Problem

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

问题描述

给定一个整数数组 nums 及两个数 k 和 t，问是否存在两个不同的下标 i 和 j 使得 |i-j|<=k 及 |nums[i]-nums[j]|<=t 同时成立。

样例

输入: nums = [1,2,3,1], k = 3, t = 0
输出: True
解释: 下标 0, 3 满足条件

解法 1

直接暴力计算，遍历下标。由于限制条件是下标之差不能超过 k，故第二层循环次数为 k，总循环次数为 nk。在 LeetCode 中直接运行会超时。但是在开始加上 t=0 时的判断以后能够击败 99% 的用户，这是因为测试样例设置的不好 (只有最后两个测试样例会超时 )，这种解法本身也是不好的。

参考代码:

class Solution:
    def contains_near_by_almost_duplicate(self, nums, k, t):
				if len(nums) < 1 or k <= 0 or t < 0:
            return False
        if t == 0 and len(nums) == len(set(nums)):
            return False
        
        for i in range(len(nums)):
            for j in range(max(0, i-k), i):
                if abs(nums[i] - nums[j]) <= t:
                    return True
        return False

解法 2

题目中有两个要求，首先是下标之差不能超过 k，其次是值之差不能超过 t。考虑对 nums 进行循环，对每一个元素 nums[i]，考察这个元素之前的 k 个元素是否有 nums[j] 满足条件。显然此时的 nums[j] 和 nums[i] 一定满足下标之差不超过 k，故需考虑第二个条件: 值之差不超过 t。

维护数组 array，其为 nums[i] 之前的 k 个元素。对于数组 array 中新增的每一个元素，通过二分法将该元素插入。由于 array 是单调递增数列，故可通过二分法查找 nums[i]-t 到 nums[i]+t 之间的元素，若存在该元素则直接返回 True 即可。

在 Python 中，可以通过二分查找与 bisect 模块 来快速进行二分插入和查找的操作。在 Java 中可以通过 TreeSet 来进行，C++ 中可以使用 multiset 来进行。