LeetCode/src/medium/ContainsDuplicateIII.java at master · chenyiAlone/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package medium;

import java.util.*;


/**
 * ClassName: ContainsDuplicateIII.java
 * Author: chenyiAlone
 * Create Time: 2019/11/28 18:31
 * Description: No.220 Contains Duplicate III
 */
public class ContainsDuplicateIII {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int size = nums.length;
        k = Math.min(k, size - 1) + 1;
        if (t < 0) return false;
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < size; i++) {
            long id = ((long)nums[i]) / ((long)t + 1);
            if (i >= k)
                map.remove(((long)nums[i - k]) / ((long)t + 1));
            if (!map.containsKey(id))
                map.put(id, 0L + nums[i]);
            else
                return true;
            if (map.containsKey(id - 1) && map.get(id) - map.get(id - 1) <= t)
                return true;
            if (map.containsKey(id + 1) && map.get(id + 1) - map.get(id) <= t)
                return true;

        }
        return false;
    }

}