Contains Duplicate III

07/16/2016 Binary Search Tree


Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.


Result: Accepted Time: 20 ms

Here should be some explanations.

class Solution {
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        const int ncnt = nums.size();
        vector<pair<int,int>> vect(ncnt);
        for(int i = 0 ; i < ncnt; i++)
            vect[i].first = nums[i],vect[i].second=i;
        for(int i = 0,j = 0; i < ncnt; j=++i)
            while( ++j < ncnt && vect[j].first - t <= vect[i].first)
                if(abs(vect[i].second-vect[j].second) <= k)
                    return true;
        return false;

Complexity Analytics

  • Time Complexity:
  • Space Complexity: