Leetcode 220 @ Contains Duplicate III

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

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

从contains duplicate I, II 做过来的。I,II都很简单，hashmap的基本做法。III的话，就是维护一个index k size 的window，找到这个window里面，只要有任意两个数的差小于等于t就可以。但是这一步怎么做呢？

我的做法是，建立一个vector<pair<int, int>> 存值和index，然后sort vector based on value。然后维护一个t size window，每个数字index差值小于等于k的，就返回。

时间复杂度 nlogn + tn => O(nlogn)

注意溢出的问题，就是假如有int_max - negavive number，就溢出了，把它们每个都cast成long.  

class Comparator
{
    public:
    bool operator() (const pair<int, int>& a, const pair<int, int> &b)
        const {
        return a.first < b.first;
    }
};
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t){
        vector<pair<int, int>> rec;
        for (int i = 0; i<nums.size(); i++)
        {
            rec.push_back({nums[i], i});
        }
        sort(rec.begin(), rec.end(), Comparator());
        for (int i = 0; i<nums.size(); i++)
        {
            int j = i+1;
            while(j < nums.size() && (long)((long)rec[j].first - (long)rec[i].first) <= t)
            {
                int dis = abs(rec[j].second - rec[i].second);
                if (dis <= k) return true;
                j++;
            }
        }
        return false;
    }
};