solved 'Contains Duplicate III' on leetcode https://leetcode.com/problems/contains-duplicate-iii/

duplicate_iii.cc

#include <cassert>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

// Inspired by 
// https://leetcode.com/discuss/45120/c-using-set-less-10-lines-with-simple-explanation
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
      set<int> appeared; 
      for(int i = 0, len = nums.size(); i < len; ++i) {
	if (i > k) {
	  // Remove element at head to keep the right window size.
	  appeared.erase(nums[i - k - 1]);
	}

	// Use long to prevent overflow.
	long curr_num = nums[i];
	// Find if there is a number in [curr - t, curr + t].
	auto in_range = appeared.lower_bound(curr_num - t);
	if (in_range != appeared.end() &&
	    *in_range <= curr_num + t) {
	  return true;
	}
	appeared.insert(nums[i]);
      }

      return false;
    }
};

int main() {
  Solution sol;
  vector<int> t;
  bool res;

  t = {1, 1};
  res = sol.containsNearbyAlmostDuplicate(t, 1, 0);
  assert(res);

  t = {};
  res = sol.containsNearbyAlmostDuplicate(t, 1, 1);
  assert(!res);

  t = {1, 3, 5};
  res = sol.containsNearbyAlmostDuplicate(t, 1, 2);
  assert(res);

  t = {1, 3, 5};
  res = sol.containsNearbyAlmostDuplicate(t, 1, -1);
  assert(!res);
}