刷题记录 - 存在重复元素 - 《学习笔记》

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:
输入: [1,2,3,1] 输出: true
示例 2:
输入: [1,2,3,4] 输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

思路：
窗口为整个数组，值判断为是否相等
用集合就可以

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (!set.add(x))
                return true;
        }
        return false;
    }
}

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:
输入: nums = [1,2,3,1], k = 3 输出: true
示例 2:
输入: nums = [1,0,1,1], k = _1 输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = _2 输出: false

思路：
窗口不再是整个数组，而是一个固定窗口k
仍然是判断是否存在值相等的两个元素
滑窗 +集合

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0, j = 0; i < nums.length; i++) {
            if (i - j > k) {
                set.remove(nums[j]);
                j++;
            }
            if (!set.add(nums[i]))
                return true;
        }
        return false;
    }
}

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0 输出：true
示例 2：
输入：nums = [1,0,1,1], k =_ _1, t = 2 输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

思路：
与上一题一样，窗口固定，区别在于不是找值相同的元素，而是找差值在某一区间内的元素
紧紧用无序集合不能快速找到区间内是否存在目标元素，只能爆搜，相当于没用。
所以得换一种数据结构，之前练习二叉树时用过二叉树解决，见二叉搜索树，问题是二叉树不是平衡树，某些情况下性能不好。
想找一个平衡二叉搜索树，于是想到可以使用TreeSet，java已经实现好的一种用红黑树实现的有序集合，插入查找，删除都可以在O(logn)内完成，效果极好。

//TreeSet
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0, j = 0; i < nums.length; i++) {
            if (i - j > k) {
                set.remove(nums[j]);
                j++;
            }
            int upper = 1L * t + nums[i] > Integer.MAX_VALUE ? Integer.MAX_VALUE : t + nums[i];     
            int down = nums[i] - 1L * t < Integer.MIN_VALUE ? Integer.MIN_VALUE : nums[i] - t;
            if (!set.isEmpty()) {
                Integer u = set.floor(upper);
                if (u != null && u >= down)
                    return true;
            }
            set.add(nums[i]);
        }
        return false;
    }
}

进阶方法：
使用桶排序，创建t+1个桶用来存放窗口内的元素，只需检查当前元素所在桶是否存在或者其与相邻的桶内元素的差值是否满足要求。
若当前元素所在桶已经存在，直接返回true，否则检查相邻桶
若相邻桶存在且元素差值满足要求，返回true，否则继续遍历下一个元素
直至所有元素被遍历完
注意：
如何将每个元素映射到每个桶？
使用哈希表来表示一个个离散的桶，桶的个数最多是窗口大小k
利用整除运算，每个桶的大小应该是t + 1，因为t - 0 >= t，满足题目差值不大于t要求。
正数使用的桶的范围从0开始，所以负数使用的桶的范围应该从-1开始，也就是需要在坐标轴上左移一位。
负数本身应该右移一位，举个例子, t = 3，那么桶的大小应设置为4，对于正数来讲
0 1 2 3 4
0 0 0 0 0 这几个数对3取模都是0，意思是都被放入0号桶
但是如果是负数
-1 -2 -3 -4
0 0 0 -1 出大问题，他们也应该落在一个桶中，所有计算某个数时需先将其右移一位。

//桶
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Long, Long> map = new HashMap<>();
        long size = t + 1L;
        for (int i = 0; i < nums.length; i++) {
            long cur = nums[i];
            long idx = get(cur, size);
            if (map.containsKey(idx)) return true;
            if (map.containsKey(idx + 1) && map.get(idx + 1) - cur <= t) return true;
            if (map.containsKey(idx - 1) && cur - map.get(idx - 1) <= t) return true;
            map.put(idx, cur);
            if (i - k >= 0) map.remove(get(nums[i - k], size));
        }
        // System.out.println(map);
        return false;
    }
    long get(long x, long size) {
        //注意这里负数的桶的选择
        return x >= 0 ? x / size : (x + 1) / size - 1;
    }
}