220. Contains Duplicate III
給定一個整數數組 nums 和兩個整數 indexDiff 和 valueDiff。
找到一對索引 (i, j) 使得：i != j
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在這樣的一對索引，返回 true；否則返回 false。
範例：
輸入：nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0 輸出：true 解釋：我們可以選擇 (i, j) = (0, 3)。 我們滿足以下三個條件：i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
Python
from sortedcontainers import SortedList
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
sorted_list = SortedList()
for i, num in enumerate(nums):
# Check if there's a number in the sorted_list within the range [num - valueDiff, num + valueDiff]
if sorted_list:
pos1 = sorted_list.bisect_left(num - valueDiff)
if pos1 < len(sorted_list) and abs(sorted_list[pos1] - num) <= valueDiff:
return True
# Add current number to the sorted list
sorted_list.add(num)
# Maintain the window of size indexDiff
if i >= indexDiff:
sorted_list.remove(nums[i - indexDiff])
return False
30.86MB, 1132ms
C++
#include <vector>
#include <set>
#include <cmath>
using namespace std;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
set<long> sortedSet;
for (int i = 0; i < nums.size(); ++i) {
// Find the position where current num can be inserted
auto pos = sortedSet.lower_bound((long)nums[i] - valueDiff);
// Check if there's a number in the sortedSet within the range [nums[i] - valueDiff, nums[i] + valueDiff]
if (pos != sortedSet.end() && *pos <= (long)nums[i] + valueDiff) {
return true;
}
// Add current number to the sorted set
sortedSet.insert(nums[i]);
// Maintain the window of size indexDiff
if (i >= indexDiff) {
sortedSet.erase((long)nums[i - indexDiff]);
}
}
return false;
}
};
128.6MB, 254ms
Javascipt
/**
* @param {number[]} nums
* @param {number} indexDiff
* @param {number} valueDiff
* @return {boolean}
*/
var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
const sortedSet = new Set();
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
// Check if there is any number in the sortedSet within the range [num - valueDiff, num + valueDiff]
for (let val of sortedSet) {
if (Math.abs(val - num) <= valueDiff) {
return true;
}
}
// Add current number to the sorted set
sortedSet.add(num);
// Maintain the window of size indexDiff
if (sortedSet.size > indexDiff) {
sortedSet.delete(nums[i - indexDiff]);
}
}
return false;
};
128.6MB, 254ms
