LC 220. Contains Duplicate III

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

这道题开始我想复杂了，我的思路是：

  1. 首先这是一个sliding window的模式，进入元素，删除元素
  2. 每次进入元素的时候，我们记录产生的差距绝对值。比如在10 33中间插入20，那么插入abs(10-20), abs(33-20).
  3. 然后删除元素的时候，将这些差距绝对值删除
  4. 然后我们每次检查差距绝对值的最小值，看看是否<=t.

其实是可以简化的，没有必要维持这个差距绝对值集合，只要每次插入的时候看看产生的差距绝对值是否<=t即可。

这题花了我好长时间，一个是思路本身就复杂，一个是操作C++ multiset出了很多问题，不容易调试。 一旦出现segfault就懵了。后来看了解答方法，觉得还是Java好写。以后写这类程序不用Python就用Java. 

import java.util.*;

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 0; i < nums.length;i ++ ) {
            int x = nums[i];
            Integer g = set.ceiling(x);
            if (g != null && ((long)g - x) <= t) {
                return true;
            }
            Integer l = set.floor(x);
            if (l != null && ((long)x - l) <= t) {
                return true;
            }
            set.add(x);
            if (set.size() > k) {
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
}

解答方法里面还给出了一种使用桶排序的方法，但是没有时间看。现在这种算法已经比较清晰简单了。