原文：220. 存在重复元素 III(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0220/

题目：

难度：Middle

相关话题：排序、Ordered Map

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j ，使得nums [i] 和nums [j] 的差的绝对值最大为 t ，并且 i 和 j 之间的差的绝对值最大为 ķ 。

示例1:

输入: nums = [1,2,3,1], k= 3, t = 0
输出: true

示例 2:

输入:nums = [1,0,1,1], k=1, t = 2
输出: true

示例 3:

输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

思路：

  1. Brute Force，按照题意逐个检查。
/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  for(let i=0;i<nums.length;i++){
    for(let j=i+1;j<=i+k;j++){
      if(Math.abs(nums[i]-nums[j])<=t)return true
    }
  }
  return false
};
  1. window slide，先按照数字大小排序，排序时保留原索引，定义一个符合t的有效区间[left,right]，一旦发现不符合nums[right]-nums[left]<=t， 说明需要left++来减小当前区间；

对当前有效区间，检查left和right的差值，如果符合k以内，返回true，如果不符合，通过right++来扩大区间，继续上面的检查区间。

这里是需要检查头和尾，对于数值，因为是有序的，检查头和尾即可；对于索引，因为窗口是不断滑动的，因此在数值符合条件的情况下，都会被检查到。

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  let aux=[]
  for(let i=0;i<nums.length;i++){
    aux.push([nums[i],i])
  }
  aux.sort((a,b)=>a[0]-b[0])

  let left=0,right=1

  while(right<aux.length){
    let diff=Math.abs(aux[right][0]-aux[left][0])
    let idxDiff=Math.abs(aux[right][1]-aux[left][1])
    if(diff<=t && idxDiff<=k){
      return true
    }else if(diff>t){
      left++
      if(left===right)right++
    }else if(idxDiff>k){
      right++
    }
  }
  return false
};
  1. 仿二叉搜索树，通过floor和ceil检测每一个值的有效性。
/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  let aux=[]
  for(let i=0;i<nums.length;i++){
    aux.push([nums[i],i])
  }
  aux.sort((a,b)=>a[0]-b[0])

  let left=0,right=1

  while(right<aux.length){
    let diff=Math.abs(aux[right][0]-aux[left][0])
    let idxDiff=Math.abs(aux[right][1]-aux[left][1])
    if(diff<=t && idxDiff<=k){
      return true
    }else if(diff>t){
      left++
      if(left===right)right++
    }else if(idxDiff>k){
      right++
    }
  }
  return false

  // 仿二叉搜索树(比较好理解)
  // 112ms
  // if(k<=0)return false
  // function bsEnd(arr,n){
  //   let lo=0,hi=arr.length-1
  //   while(lo<hi){
  //     let mid=Math.floor((lo+hi)/2)
  //     if(arr[mid][0]<n)lo=mid+1
  //     else hi=mid
  //   }
  //   return hi
  // }
  // function bsFront(arr,n){
  //   let lo=0,hi=arr.length-1
  //   while(lo<hi){
  //     let mid=Math.ceil((lo+hi)/2)
  //     if(arr[mid][0]>n)hi=mid-1
  //     else lo=mid
  //   }
  //   return lo
  // }
  // let aux=[]
  // for(let i=0;i<nums.length;i++){
  //   aux.push([nums[i],i])
  // }
  // // 排序后才能进行二分搜索
  // aux.sort((a,b)=>a[0]-b[0])
  // for(let i=0;i<aux.length;i++){
  //   let [v,idx]=aux[i]
  //   let floor=bsFront(aux,v+t),
  //       ceil=bsEnd(aux,v-t)
  //   // floor指的是小于等于v+t的所有的数字中最大的
  //   if(floor!==i &&
  //      aux[floor][0]>=v &&
  //      aux[floor][0]<=v+t &&
  //      Math.abs(aux[floor][1]-idx)<=k)
  //     return true
  //   // ceil指的是大于等于v-t的所有数字中最小的
  //   if(ceil!==i &&
  //      aux[ceil][0]<=v &&
  //      aux[ceil][0]>=v-t &&
  //      Math.abs(aux[ceil][1]-idx)<=k)
  //     return true
  // }
  // return false
};

扩展阅读：