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;
    }
}

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