Leetcode 220. 存在重复元素 III 解题思路及C++实现

    xiaoxiao2023-11-07  156

    解题思路:

    使用set集合来实现滑动窗口k,对窗口内的数进行比较,得到结果。

    使用两个指针i、j,来确定窗口位置,i走在前面,j在后面。因为数组内这两个数的差值绝对值限制为:| x - nums[i] | < t,所以,有 nums[i] - t < x < nums[i] + t,所以,我们要在set s中找到nums[i] - t所在的位置,如果找到了,说明窗口内有满足这左侧不等式的数x,再判断右侧不等式x < nums[i] + t是否满足,如果均满足,即找到,返回true。如果不满足其一,就将窗口向右平移一位。

    主要使用了lower_bound函数。

     

    class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long long> s; for(int i = 0, j = 0; i < nums.size(); i++){ if(i - j > k){ s.erase(nums[j++]); } auto it = s.lower_bound((long long)nums[i] - t); if(it != s.end() && abs(*it - nums[i]) <= t) return true; s.insert(nums[i]); } return false; } };

     

     

    最新回复(0)