中文绿色环保网站模板,网页制作入门视频教程,在线制作简历模板免费,有赞微商城登录入口220. 存在重复元素 III
题目描述#xff1a; 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j#xff0c;使得 abs(nums[i] - nums[j]) t #xff0c;同时又满足 abs(i - j) k 。
如果存在则返回 true#xff0c;不存在返回 …220. 存在重复元素 III
题目描述 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j使得 abs(nums[i] - nums[j]) t 同时又满足 abs(i - j) k 。
如果存在则返回 true不存在返回 false。
考察重点滑动窗口桶排序
方法概括滑动窗口循环i向后一位则删除一个之前存在桶中的第i-k元素。桶排序根据特定条件将不同元素放入不同队列中(本题中用的是hashmap)
/**
桶排序思想以t 1 作为桶基准来区分元素如数列 1 4 8 9 12 14 16 如果t为3 则t1为4 bucket n / (t1)放入桶 0 1 2 2 3 3 4 桶只存放满足满足条件并且靠后的元素(索引2 索引3 同样在桶2,因为是向后遍历所以存相对靠后的索引3元素即可)
*/
func ContainsNearbyAlmostDuplicate(nums []int, k int, t int) bool {numslen : len(nums)bucket : make(map[int]int, numslen)for i : 0; i numslen; i {id : getId(nums[i], t)_, ok : bucket[id]if ok { //如果相同桶中有元素直接返回return true}v, ok : bucket[id1]if ok abs(nums[i]-v) t { //如果是相邻桶中有元素考虑有6/32 5/31这种情况 所以还需要具体比较两元素是否差值treturn true}v, ok bucket[id-1]if ok abs(nums[i]-v) t {return true}bucket[id] nums[i]if i k { //精髓滑动窗口一边向后遍历一边删除当前位置之前k位即不满足i-j k的元素delete(bucket, getId(nums[i-k], t))}}return false
}func abs(n int) int {if n 0 {return n} else {return -n}
}func getId(n int, k int) int {if n 0 {return n / (k 1)}return n/(k1) - 1 //精髓因为如果abs(n) k 比如-2 / 3 与 2 / 3 都会返回0而负值-1则会将-2/3返回-1。由此将-2与2区分开来
} //同时因为所有负数统一-1也不会影响其他负数。比如-4/3 将返回-2
