存在重复元素

in Algorithm Pageviews

solve actually problem!

给定一个整数数组 nums 和两个整数 indexDiff 和 valueDiff。找出的满足下述条件的下标对(i, j):

  • i != j
  • abs(i - j) <= indexDiff
  • abs(nums[i] - nums[j]) <= valueDiff

如果存在，则返回true；否则，返回false。

示例1：

输入：nums = [1,2,3,1]，indexDiff = 3, valueDiff = 0

输出：true

解释：可以找出 (i, j) = (0, 3);

  • i != j
  • abs(i - j) <= indexDiff <—> abs(0, 3) <= 3
  • abs(nums[i] - nums[j]) <= valueDiff <—> abs(1 - 1) <= 0

示例2：

输入：nums = [1, 5, 9, 1, 5, 9]，indexDiff = 2，valueDiff = 3

输出：false

解释：尝试所有可能的下标对(i, j)，都无法满足这3个条件，因此返回false

class Solution {
public:
    bool ContainsNearbyAlmostDuplicate(vector<int> &nums, int indexDiff, int valueDiff)
    {
        int right = 0;
        multiset<long> win;
        while (right < nums.size()) {
            if (right > indexDiff) {
                win.erase(nums[right - indexDiff - 1]);
            }

            auto numIter = win.lower_bound(nums[right] - indexDiff);
            if ((numIter != win.end()) && ((*numIter - nums[right]) <= valueDiff)) {
                return true;
            }
            win.insert(nums[right++]);
        }
        return false;
    }
};