高效判断整数数组中是否存在满足条件的元素对

本文将介绍如何判断给定的整数数组 nums 中是否存在两个不同的下标 i 和 j，满足以下条件：

i != j2. abs(i - j) <= indexDiff3. abs(nums[i] - nums[j]) <= valueDiff

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

C++ 代码实现

以下是一个时间复杂度为 O(n^2) 的算法，使用结构体的方式实现判断是否存在满足条件的两个下标 (i, j)：cpp#include #include

struct Pair { int num; int index;};

bool checkPairs(const std::vector& nums, int indexDiff, int valueDiff) { std::vector pairs;

for (int i = 0; i < nums.size(); i++) {        pairs.push_back({nums[i], i});    }

for (int i = 0; i < pairs.size(); i++) {        for (int j = i + 1; j < pairs.size(); j++) {            int indexDist = std::abs(pairs[i].index - pairs[j].index);            int valueDist = std::abs(pairs[i].num - pairs[j].num);            if (indexDist <= indexDiff && valueDist <= valueDiff) {                return true;            }        }    }

return false;}

代码解释

该算法首先将输入的数组 nums 转换为包含每个元素和对应下标的结构体 Pair 的向量 pairs。然后，通过两层循环遍历所有可能的组合，并计算两个下标和对应数值的差距。如果找到满足条件的两个下标，即 indexDist <= indexDiff 和 valueDist <= valueDiff，则返回 true。如果没有找到满足条件的两个下标，则返回 false。

时间复杂度

该算法的时间复杂度为 O(n^2)，其中 n 是数组的长度。在最坏情况下，需要遍历所有可能的组合。因此，如果数组较大，可能需要考虑进一步的优化，例如使用哈希表等数据结构。