b_lc_存在重复元素III(order哈希表的查询)

判断A中是否有两个位置的数满足(A.length<=2e4):

  • 索引绝对值差不超过k
  • 绝对值差不超过t

思路从前往后遍历,维护一个大小不大于k的窗口,这样在窗口内查找A[i]-t、A[i]+t的值就很方便

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

还可以优化的一点是:直接找≥A[i]-t的元素y,然后判断是否≤A[i]+t即可,因为

x-t      x      x+t
     y1
         y2  y3
上一篇:博客索引


下一篇:【LeetCode】216. 组合总和 III(回溯)