当前位置：首页 > news >正文

Contains Duplicate III

news 来源：原创 2024/5/7 12:17:11

题目描述：

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

就是给定1个数组nums，以及索引最大间隔k，和值最大间隔t，在nums数组内，找出是否存在num[i],和nums[j]，其中i,j ∈[0,nums.Length-1]，使得 abs(i-j) <= k 并且 abs(nums[i]-nums[j]) <= t

思路：
1. 遍历nums数组，使用BST来存nums[i]在k范围内所有可达的数
2. 使用SortedSet<T>这个数据结构来存放从i到k范围内的每个数，由于SortedSet的内部实现是平衡树
(http://stackoverflow.com/questions/3262947/is-there-a-built-in-binary-search-tree-in-net-4-0)，因此它的增删查都是log(n)，所以算上外循环，总体复杂度是n*log(n)
3. 确定要查找的边界：
min = nums[i] - t; // 可取的最小值
max = nums[i] + t; // 可取的最大值

4. 如果sortedSet的长度大于 k，删除第一个，只需要维护长度为k的数据就可以了

实现代码：

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    	if(k < 1 || t < 0){
			return false;
		}
		
		if(nums == null || nums.Length == 1)
    	{
    		return false;
    	}
		
		var map = new SortedSet<int>();
		
        for(var i = 0 ;i < nums.Length; i++)
		{
		    if(nums[i] > Int32.MaxValue){
				return false;
			}
			
			if(map.Count > k){
				map.Remove(nums[i-k-1]);
			}
			
			var max = nums[i] + t;
			if(nums[i] > 0 && max < 0){
				max = Int32.MaxValue;
			}
			
			var min = nums[i] - t;
			
			var found = map.GetViewBetween(min,max);
			if(found.Count > 0){
				return true;
			}


			map.Add(nums[i]);
       }
	   
       return false;
    }
}