# 220. Contains Duplicate III

Description:

https://leetcode.com/problems/contains-duplicate-iii/#/description

Algorithm:

• Use vector<pair<int, int>> to solve this problem.
• Learn how to define comparison rules for std::sort()
• sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; });

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

comp:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to `bool`.

The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Why there is a green []?????

Code:

```class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { const int n = nums.size(); vector<pair<int, int>> pairs; // a vector of (value, index) pairs pairs.reserve(n); for (int i = 0; i < n; ++i) pairs.emplace_back(nums[i], i); sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; }); for (int i = 0; i < n - 1; ++i) for (int j = i + 1; j < n; ++j) if ((long long)pairs[j].first - pairs[i].first <= t) { if (abs(pairs[j].second - pairs[i].second) <= k) return true; } else break; return false; } };```

Time & Space: