220. Presence of repeating element III

For this question , Because the question is limited abs(i - j) <= k Conditions , You should first think of sliding windows , Because sliding window can meet this limit . Conduct relevant operations on the data in the window to judge whether there is data in line with the meaning of the question

First, the size of the window should be k, This can meet the abs(i - j) <= k Conditions .

secondly , For the data in the window , You can use two for Loop to judge whether there is a combination that meets the meaning of the question . Because what is required in the question is the absolute value of subtraction , So for for loop , You can save half the cycle , because |a - b | = |b - a|

Here are Go The language code ：

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    
	if k >= len(nums) {
    
		k = len(nums) - 1
	}
	for start := 0; start+k < len(nums); start++ {
    
		subArr := nums[start : start+k+1]
		for i := 0; i <= k; i++ {
    
			for j := i + 1; j <= k; j++ {
    
				if abs(subArr[i]-subArr[j]) <= t {
    
					return true
				}
			}
		}
	}
	return false
}

func abs(num int) int {
    
	if num < 0 {
    
		return -num
	}
	return num
}

however , The time complexity of the implementation of violent solution is too high , Cause execution timeout

therefore , The time-consuming part of this algorithm needs to be optimized . For the optimization of the algorithm , Thinking is nothing more than the transformation of time and space . We want to reduce the time complexity , It can be done by increasing the spatial complexity .

Look back at the code above , The most time-consuming operation is to determine whether there is abs[i] - abs[j] <= t, For this operation , The above code uses the exhaustive method , The time complexity is O(n²), If we change to the idea of bucket sorting , The operation time complexity of this part can be reduced to O(n)

We can maintain multiple lengths t+1 The barrel , If two elements fall into a bucket at the same time , It means that the conditions in the question are met , If it falls into two adjacent barrels , You need to judge whether the absolute value of the subtraction of these two values meets the meaning of the question .

As shown in the following figure ：

because t = 3 Then the number 0 - 3 Get a bucket ,4 -7 Get a bucket ,8 - 11 Get a bucket

For the first sliding window , Because the length is 3, So intercept the first three elements , These three elements correspond to three barrels

When putting the first element , Assigned to the first bucket , And there are no elements in the adjacent barrels .

When putting the second element , The first bucket next to it contains elements , but 5 - 1 > 3 So not satisfied

When putting the third element , The second bucket next to it contains elements , but 9 - 5 > 3 So not satisfied

And so on sliding window , Not satisfied until the end , So back false

Corresponding Go The code is as follows ：

func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
    
	mp := map[int]int{
    }
	for i, x := range nums {
    
		id := getID(x, t+1)
		if _, has := mp[id]; has {
    
			return true
		}
		if y, has := mp[id-1]; has && abs(x-y) <= t {
    
			return true
		}
		if y, has := mp[id+1]; has && abs(x-y) <= t {
    
			return true
		}
		mp[id] = x
		if i >= k {
    
			delete(mp, getID(nums[i-k], t+1))
		}
	}
	return false
}

func getID(x, w int) int {
    
	if x >= 0 {
    
		return x / w
	}
	return (x+1)/w - 1
}

func abs(x int) int {
    
	if x < 0 {
    
		return -x
	}
	return x
}

For the above code , People who have seen it may have two questions ：

1. For each barrel , Not saved in array , Instead, only one value is saved , Are you not afraid of being covered, which will cause other barrels to be adjacent to this barrel but not get the correct results ？

 If coverage occurs here , Will go straight back to true Of , So there is no such situation .

2.getID about x<0 Some of them don't understand why .

 For greater than 0 Part of , if t = 3  be  0-3,4-7,8-11... It's a group. 
 But for less than 0 Part of , In principle, it should be  -4 - -1,-8 - -5 ... It's a group. , But if you follow x>=0 The method of calculation , be  -4  And  -1 Divided into two groups . So we need to +1, Turn it into  -3 - 0 Keep consistent with positive numbers to group , After grouping -1, And 0-9 Medium 0 Make a difference . The result is just  -4 - -1 This group